Code
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 597 Accepted Submission(s): 230
The function:
int calc { int res=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { res+=gcd(a[i],a[j])*(gcd(a[i],a[j])-1); res%=10007; } return res;
}
For each case:
The first line contains an integer N(1≤N≤10000).
The next line contains N integers a1,a2,...,aN(1≤ai≤10000).
Print an integer,denoting what the function returns.
1 3 4 2 4
gcd(x,y) means the greatest common divisor of x and y.
题意：就是给你一系列数，让找两个数最大公约数x,求所有x（x-1）的和；其实就是一个容斥，对于每给的一个数，找里面因子出现的次数；
现在我们的任务就是给你一个x为gcd，找以x为gcd出现的次数，最多有count[x]^2次，需要减去多考虑的也就是 2x, 3x, 4x...出现的次数；
f[i]代表以i为gcd出现的次数；
/**********/
首先的思路是，考虑每个数对最终答案的贡献。
那么我们就要求出：对于每个数，以它为 gcd 的数对有多少对。
显然，对于一个数 x ，以它为 gcd 的两个数一定都是 x 的倍数。如果 x 的倍数在数列中有 k 个，那么最多有 k^2 对数的 gcd 是 x 。
同样显然的是，对于两个数，如果他们都是 x 的倍数，那么他们的 gcd 一定也是 x 的倍数。
所以，我们求出 x 的倍数在数列中有 k 个，然后就有 k^2 对数满足两个数都是 x 的倍数，这 k^2 对数的 gcd，要么是 x ，要么是 2x, 3x, 4x...
并且，一个数是 x 的倍数的倍数，它就一定是 x 的倍数。所以以 x 的倍数为 gcd 的数对，一定都包含在这 k^2 对数中。
如果我们从大到小枚举 x ，这样计算 x 的贡献时，x 的多倍数就已经计算完了。我们用 f(x) 表示以 x 为 gcd 的数对个数。
那么 f(x) = k^2 - f(2x) - f(3x) - f(4x) ... f(tx) (tx <= 10000, k = Cnt[x])
这样枚举每个 x ，然后枚举每个 x 的倍数，复杂度是用调和级数计算的，约为 O(n logn)。
/*********/
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int INF=0x3f3f3f3f;
#define mem(x,y) memset(x,y,sizeof(x))
typedef long long LL;
const int MAXN=10010;
const int MOD=10007;
int cnt[MAXN],f[MAXN];
int main(){
int N;
while(~scanf("%d",&N)){
int x;
mem(cnt,0);mem(f,0);
for(int j=0;j<N;j++){
scanf("%d",&x);
for(int i=1;i<=(int)sqrt(x);i++){
if(x%i==0){
cnt[i]++;
if(x/i!=i)cnt[x/i]++;
}
}
}
int ans=0,temp=0;
for(int i=10000;i>=1;i--){
f[i]=cnt[i]*cnt[i]%MOD;
for(int j=i*2;j<=10000;j+=i)
f[i]=(f[i]-f[j]+MOD)%MOD;
temp=i*(i-1)%MOD;
ans=(ans+f[i]*temp%MOD+MOD)%MOD;
}
printf("%d\n",ans);
}
return 0;
}