输入正整数 \(n\),求 \(gcd(1,2)+gcd(1,3)+gcd(2,3)+...+gcd(n-1,n)\)，即所有满足 \(1\leq i<j\leq n\) 的所有正整数对 \((i,j)\) 所对应的 \(gcd(i,j)\) 之和。
Solution设 \(f(n)=gcd(1,n)+gcd(2,n)+...+gcd(n-1,n)\)，则所求答案为 \(ans(n)=f(2)+f(3)+f(4)+...+f(n)\)。只需求出 \(f(n)\)，就可以递推出所有答案：\(ans(n)=ans(n-1)+f(n)\)。因此，本题的重点在于如何计算 \(f(n)\)。
注意到所有 \(gcd(x,n)\) 的值都是 \(n\) 的约数，可以按照这个约数进行分类，用 \(g(i,n)\) 表示满足 \(gcd(x,n)=i\;\&\&\;x<n\) 的正整数 \(x\) 的个数，则 \(f(n)=\sum \limits_{i\mid n} g(i,n)\times i\)。注意到 \(gcd(x,n)=i\) 的充要条件是 \(gcd(x/i,n/i)=1\)，因此满足条件的 \(x/i\) 有\(phi(n/i)\) 个，说明 \(gcd(x,n)=phi(n/i)\)。
所以对于每个数 \(i\)，枚举它的倍数 \(j\)，令 \(f(j)+=i\times phi(j/i)\) 即可。
Code#include<cstdio> #define N 4000005 #define int long long int phi[N]; int mindiv[N]; int f[N],ans[N]; int prime[N],primecnt; void init(){ for(int i=2;i<=N;i++){ if(!mindiv[i]){ phi[i]=i-1; mindiv[i]=i; prime[++primecnt]=i; } for(int j=1;j<=primecnt;j++){ if(i*prime[j]>N) break; if(prime[j]>mindiv[i]) break; mindiv[i*prime[j]]=prime[j]; phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]); } } } signed main(){ init(); for(int i=1;i<=N;i++){ for(int j=(i<<1);j<=N;j+=i) f[j]+=phi[j/i]*i; } ans[2]=f[2]; for(int i=3;i<=N;i++) ans[i]=ans[i-1]+f[i]; int x; while(scanf("%lld",&x)){ if(!x) return 0; printf("%lld\n",ans[x]); } return 0; }