BZOJ2705 Longge的问题

代码

//ms
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans=,n;
ll phi(ll n){
    int ret=,i;
    for(i=;i*i<=n;i++){
        if(n%i==){
            n/=i,ret*=i-;
            while(n%i==)n/=i,ret*=i;
        }
    }
    if(n>)ret*=n-;
    return ret;
}
int main(){
    scanf("%lld",&n);
    for(int i=;i*i<=n;i++)
        if(n%i==){
            ans+=(ll)i*phi(n/i);
            if(i*i<n) ans+=(ll)n/i*phi(i);
        }
    printf("%lld",ans);
    return ;
}
           

//【转】8ms
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n,p,a,ans;
    while (cin >>n){
        ans=n;
        for (long long i=;i*i<=n;i++){
            if (n%i==) {
                p=i;a=;
                while (n%p==)a++,n/=p;
                ans+=ans*a*(p-)/p;
            }
        }
        if(n!=)ans=ans*(n*-)/n;
        cout<<ans<<endl;
    }
    return ;
}
           

题解

有j = gcd(i,n)的个数为phi(n/j)？