Luogu P2303 [SDOI2012] Longge 的问题 解题报告
求
\sum\limits_{i=1}^n \gcd(i, n)
n \leq 2 ^ {32}
解题思路:
数学题。(第一次推出式子来真的好开心hhhh)
首先看到 gcd ,第一反应应该是从
那么我们把
我们要求的东西其实就是
化简一波式子:
然后直接算就行了。
时间复杂度
代码:
ll n,ans;
ll phi(int x) {
if (x == 1) return 1;
ll ans = x;
for (int i = 2;i *i <= x;++i) {
if (x % i == 0) {
while (x % i == 0) {x /= i;}
ans = (ans * (i-1) / i);
}
}
if (x > 1) ans = (ans * (x-1) / x);
return ans;
}
signed main() {
read(n);
for (int i = 1;i * i <= n;++i) {
if (n % i == 0) {
ans += i*phi(n/i);
if (i * i != n) ans += n/i * phi(i);
}
}
printf("%lld",ans);
return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭