bzoj 2705: [SDOI2012]Longge的问题

题目链接

题解

[sum_{i = 1}^ngcd(i,n) = sum_d dsum_{i = 1}^n(gcd(i,n) = d) ]

[= sum_d dsum_{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
",ans); 
    return 0; 
}