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

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

​​     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 #include 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&&n){ LL ans=0; for(int i=1;i<=n;i++) ans+=f[i]; printf("%lld\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。