51nod1040最大公约数之和（欧拉函数）

向右看齐 2021-12-23 05:31 127阅读 0赞

## 题面 ##

[传送门][Link 1]

## 题解 ##

这种题目就是推倒推倒

\\\[\\sum\_\{i=1\}^n \\gcd(i,n)=\\sum\_\{i|n\}i\\sum\_\{j=1\}^n\[\\gcd(j,n)=i\]\\\]

\\\[\\sum\_\{i=1\}^n \\gcd(i,n)=\\sum\_\{i|n\}i\\sum\_\{j=1\}^\{\\frac\{n\}\{i\}\}\[\\gcd(j,\\frac\{n\}\{i\})=1\]\\\]

\\\[\\sum\_\{i=1\}^n \\gcd(i,n)=\\sum\_\{i|n\}i\\varphi(\{\\frac\{n\}\{i\}\})\\\]

然后暴力就行了

//minamoto
    #include<bits/stdc++.h>
    #define R register
    #define ll long long
    #define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
    #define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
    #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
    using namespace std;
    const int N=1e5+5;
    bitset<N>vis;int p[N],phi[N],c[N],v[N],top,n,m,t,sqr;ll res;
    void init(int n){
        phi[1]=1;
        fp(i,2,n){
            if(!vis[i])p[++m]=i,phi[i]=i-1;
            for(R int j=1;j<=m&&1ll*i*p[j]<=n;++j){
                vis[i*p[j]]=1;
                if(i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];break;}
                phi[i*p[j]]=phi[i]*(p[j]-1);
            }
        }
    }
    int Phi(int n){
        if(n<=sqr)return phi[n];
        int res=n;
        for(R int i=1;i<=m&&p[i]<=n;++i)if(n%p[i]==0){
            while(n%p[i]==0)n/=p[i];
            res=res/p[i]*(p[i]-1);
        }
        if(n!=1)res=res/n*(n-1);
        return res;
    }
    void dfs(int pos,int now){
        if(pos==top+1)return res+=1ll*now*Phi(n/now),void();
        for(int i=0;i<=c[pos];++i,now*=v[pos])dfs(pos+1,now);
    }
    int main(){
    //  freopen("testdata.in","r",stdin);
        scanf("%d",&n),init(sqr=N-5);
        t=n;
        fp(i,1,m)if(t%p[i]==0){
            v[++top]=p[i];
            while(t%p[i]==0)++c[top],t/=p[i];
        }
        if(t!=1)v[++top]=t,c[top]=1;
        dfs(1,1);
        printf("%lld\n",res);
        return 0;
    }

转载于:https://www.cnblogs.com/bztMinamoto/p/10428230.html

[Link 1]: http://www.51nod.com/Challenge/Problem.html#!%23problemId=1040