1902: 985的因子对难题

1902: 985的因子对难题

Time Limit: 2 Sec   Memory Limit: 128 MB Submit: 150   Solved: 42 Submit Status Web Board

Description

985有n个正整数，他想知道存在多少个不同的因子对(a[i], a[j])使得 1 <= i, j <= n && i != j && a[j] % a[i] == 0，其中i和j是元素的下标。 特别地，他认为（a[i]，a[j]）与（a[j]，a[i]）是一样的因子对。

Input

第一行输入一个整数t，代表有t组测试数据。 每组数据占两行，第一行输入一个n代表元素个数，下面一行输入n个整数a[]。 注：1 <= t <= 30，1 <= n <= 1e5，1 <= a[] <= 1e6。

Output

一个整数代表最后的答案。

Sample Input

251 2 3 4 552 2 2 2 2

Sample Output

510 #include<stdio.h> #include<string.h> int num[1000010],ans[1000010];num[i]记录i出现的次数，ans[i]记录i的因数的个数，不包括本身 int main() { int t,n,a,i,j; long long sum; scanf("%d",&t); while(t--) { memset(num,0,sizeof(num)); memset(ans,0,sizeof(ans)); scanf("%d",&n); int max=0; while(n--) { scanf("%d",&a); num[a]++; if(max<a) max=a; } for(i=1;i<=max;i++) { if(!num[i]) continue; else { for(j=2*i;j<=max;j+=i) ans[j]+=num[i]; } } sum=0; for(i=1;i<=max;i++) sum+=num[i]*(num[i]-1)/2;\\i可以与非本身的num[i]-1个i组成因子对 for(i=1;i<=max;i++) sum+=num[i]*ans[i]; printf("%lld\n",sum); } return 0; }