题意： 输入n个数， 求这n个数的n^2个两两组合的最大公约数x，x(x-1)之和 。 换个思路， 我们如果求出了最大公约数为x的对数cnt， 那么答案就增加x(x-1)cnt^2 那么怎么求以x为最大公约数的对数呢？ 我们枚举x的整数倍， 这样就可以知道这些数中是x的整数倍的数有多少个。 那么到底哪些数才是x的最大公约数呢？   显然， 应该满足：能被x正处而不能被x的倍数整除。 假设能被x整除的数有k1个，能被2x整除的数有k2个， 能被3x整除的数有k3个...... 所以gcd() == x 的数就是  k1 - k2 - k3 ....... 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) a>b?a:b #define Min(a,b) a<b?a:b using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int mod = 10007; const int maxn = 10000+5; int T,n,m; ll a[maxn],cnt[maxn],d[maxn]; int main() { while(~scanf("%d",&n)) { ll maxv = 0; memset(cnt, 0, sizeof(cnt)); memset(d, 0, sizeof(d)); for(int i=0;i<n;i++) { scanf("%I64d",&a[i]); cnt[a[i]]++; maxv = max(maxv, a[i]); } ll ans = 0; for(int i=2;i<=maxv;i++) { for(int j=i;j<=maxv;j+=i) { d[i] += cnt[j]; } d[i] *= d[i]; } for(ll i=maxv; i>1; i--) { for(int j=i*2;j<=maxv;j+=i) { d[i] -= d[j]; } ans = (ans+(i*(i-1))*d[i]%mod)%mod; } printf("%d\n",ans); } return 0; } ~~~