bzoj 2705: [SDOI2012]Longge的问题 欧拉函数

感觉自己就像一个zz一样,最初写了10^6的筛法求欧拉函数,自己还好奇为什么re了。。。。。

我们可以考虑枚举gcd等于多少,然后变成了

Σ d|nΣ(d * [gcd(j,n) == d] (1<= j <= n))

Σ d|nΣ(d * [gcd(j,n / d) == 1] (1<= j <= n / d))

显然gcd(j,n/d)的数量可以使用欧拉函数计算。

 

 

我们在根号n的时间内枚举每个因子,然后phi可以在根号时间内算出即可。

发表评论