输入正整数 \(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;
- }
来源: https://www.cnblogs.com/YoungNeal/p/9102468.html