題意： 輸入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; } ~~~