题目链接
bzoj 2705: [SDOI2012]Longge的问题
题解
\[\sum_{i = 1}^ngcd(i,n) = \sum_d d\sum_{i = 1}^n(gcd(i,n) = d)\]\[ = \sum_d d\sum_{i = 1}^{\frac{n}{i}}(gcd(i,\frac{n}{d}) = 1） = \sum_d d \phi(\frac{n}{d})\] 根n枚举约数根n求phi 感觉复杂度有点高，实际不满
代码
#include<cstdio>
#include<algorithm>
#define LL long long
LL n;
LL ans = 0;
LL phi(LL x) {
LL ret = 1;int tot = 0 ;
for(int i = 2;1ll * i * i <= x;++ i) {
if(x % i) continue;
ret *= 1ll * (i - 1); x /= i;
while(!(x % i)) x /= i,ret *= i;
}
if(x > 1) ret *= 1ll * (x - 1);
return ret;
}
int main() {
scanf("%lld",&n);
for(int i = 1;1ll * i * i <= n;++ i) {
if(n % i == 0) {
LL x = n / i;
ans += 1ll * phi(n / i) * i;
if(i * i != n)ans += 1ll * phi(n / x) * x;
}
}
printf("%lld\n",ans);
return 0;
}
转载于:https://www.cnblogs.com/sssy/p/9157276.html
