uva 11426 GCD - Extreme (II) （神奇的GCD）

本文主要是介绍uva 11426 GCD - Extreme (II) （神奇的GCD），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2421

大意：给定正整数N，求出

for(i=1;i<N;i++)
     for(j=i+1;j<=N;j++)
        G+=gcd(i,j);

G的值。

分析：老样子，举例看规律

     n=3   贡献的公约数：1*2

     n=6   贡献的公约数：2*2

     n=9   贡献的公约数：3*2

所以我们可以这样想，对N素因子分解，然后用得到的一个个素因子去计算所有n的公约数贡献值。

比如上面，p=3.

n=3,  ans+=phi(3)*1;

n=3*2, ans+=phi(3)*2

n=3*3, ans+=phi(3)*3.

设一个数组f[]，f(i*j)+=phi(i)*j.

最后累加。

#include <iostream>
#include <cstdio>
using namespace std;
const int N=4e6+10;
typedef long long LL;
int phi[N];
LL f[N];
void getphi(){for(int i=1;i<N;i++)    phi[i]=i;for(int i=2;i<N;i++){if(phi[i]==i){for(int j=i;j<N;j+=i){phi[j]=phi[j]-phi[j]/i;}}for(int j=1;j*i<N;j++){f[j*i]+=j*phi[i];}}
}
int main()
{//freopen("cin.txt","r",stdin);getphi();int n;while(cin>>n&&n){LL ans=0;for(int i=1;i<=n;i++)  ans+=f[i];printf("%lld\n",ans);}return 0;
}

这篇关于uva 11426 GCD - Extreme (II) （神奇的GCD）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---