链接：http://www.cnblogs.com/JoeFan/p/4458629.html
这道题需要一些莫比乌斯反演、线性筛的知识
定义f(x)=x?(x?1)
题目所求即为sigma(f(gcd(ai,aj)|i!=j,1≤i,j≤n)
先用线性筛求出miu在[1,10000]的函数值
利用莫比乌斯反演公式我们可以O(vlogv)暴力求解出函数g在[1,10000]的函数值，其中g满足：
sigma(g(d)|x
这样所求答案即为：
sigma(g(d)?cnt(d)?cnt(d)|1≤d≤10000)，其中cnt函数满足：
cnt(x)=在a1,a2,..,an中是x的倍数的个数
而cnt的取值也可以O(vlogv)暴力计算出
所以总的时间复杂度就是O(vlogv)的
分析：首先，我们分析每个数对最终答案的影响。
那么我们就要求出：对于每个数，以它为 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<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<string>
#include<cstdlib>
#include<cmath>
//#include<bits/stdc++.h>
using namespace std;
template<class T>inline T read(T&x)
{
char c;
while((c=getchar())<=32)if(c==EOF)return 0;
bool ok=false;
if(c=='-')ok=true,c=getchar();
for(x=0; c>32; c=getchar())
x=x*10+c-'0';
if(ok)x=-x;
return 1;
}
template<class T> inline T read_(T&x,T&y)
{
return read(x)&&read(y);
}
template<class T> inline T read__(T&x,T&y,T&z)
{
return read(x)&&read(y)&&read(z);
}
template<class T> inline void write(T x)
{
if(x<0)putchar('-'),x=-x;
if(x<10)putchar(x+'0');
else write(x/10),putchar(x%10+'0');
}
template<class T>inline void writeln(T x)
{
write(x);
putchar('\n');
}
//-------ZCC IO template------
const int maxn=1e4+10;
const double inf=99999999;
#define lson (rt<<1),L,M
#define rson (rt<<1|1),M+1,R
#define M ((L+R)>>1)
#define For(i,t,n) for(int i=(t);i<(n);i++)
typedef long long LL;
typedef double DB;
typedef pair<int,int> P;
#define bug printf("---\n");
#define mod 10007
int yinzhi[maxn];
int f[maxn];
int main()
{
int n;
while(read(n))
{
memset(yinzhi,0,sizeof(yinzhi));
For(i,0,n)
{
int a;
read(a);
for(int j=1; j*j<=a; j++)
{
if(a%j==0)
{
yinzhi[j]++;
if(j*j!=a)
yinzhi[a/j]++;
}
}
}
int ans=0;
for(int i=10000; i>=1; i--)
{
f[i]=(yinzhi[i]*yinzhi[i])%mod;
for(int j=i*2; j<=10000; j+=i)
{
f[i]=(f[i]-f[j]+mod)%mod;
}
int p=i*(i-1)%mod;
ans=(ans+p*f[i]%mod)%mod;
}
writeln(ans);
}
return 0;
}
/*
6
12 5 4 6265 6 45
*/
原文：http://blog.csdn.net/u013167299/article/details/45317533