1.题目

biubiu

2.题解

这题不能直接预处理出phi,因为数组开不下。。

设gcd(i,n)==k ->gcd(i/k,n/k)==1 。

所以i/k有phi[n/k]种选法 。

ans=sigma(phi[k])1<=k<=n;

还是过不了。。。

设f[d]为gcd(i,n)==d的方案数,d是n的约数

ans=sigma(d×f[d]) !

枚举约数d,可以在sqrt(d)内求phi(d)

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>void read(T &in){
    char c=getchar();int f=1;in=0;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){in=in*10+c-'0';c=getchar();}
    in*=f;
}
ll n,m,ans;
ll phi(ll x){
    ll t=x;
    for(int i=2;i<=m;++i){
        if(x%i==0){
            t=t/i*(i-1);
            while(x%i==0)x/=i;
        }
    } 
    if(x>1)t=t/x*(x-1);
    return t;
}
int main(){
    freopen("a.in","r",stdin);
    read(n);m=sqrt(n);
    for(int i=1;i<=m;++i){
        if(n%i==0){
            ans+=(ll)i*phi(n/i);
            if(i*i<n)ans+=(ll)(n/i)*phi(i);
        }
    }
    printf("%lld",ans);
    return 0;
}
分类: 文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *