BUPT 2017 summer training (for 16) #1D

题意

找到n个数里面有多少对具有倍数关系。\(1 ≤ n ≤ 10^4，2 ≤ a_i ≤ 10^6\)

题解

枚举一个数，和它的倍数。

代码

#include <cstdio>

#include <cstring>

int n,t,b[1000001];

int main(){

    scanf("%d",&t);

    while(t--){

        memset(b,0,sizeof b);

        scanf("%d",&n);

        for(int i=1,a;i<=n;++i){

            scanf("%d",&a);

            ++b[a];

        }

        int ans=0;

        for(int i=2;i<=1000000;++i)if(b[i]){

            ans+=b[i]*(b[i]-1)/2;

            for(int j=i*2;j<=1000000;j+=i)

                ans+=b[i]*b[j];

        }

        printf("%d\n",ans);

    }

    return 0;

}