欧拉函数和费马小定理（基础题题解）

Bertha 。 2022-09-29 05:21 178阅读 0赞

太久没有在blog上记录学习进度啦，需要认真反思一下，陈老师的话如同醍醐灌顶，复习知识唤醒记忆，拥有一个属于自己的blog是一件引以为豪的事情，希望自己做的越来越好吧！加油！

poj 2407 Relatives

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    long long phi(long long n)
    {
        long long res=n;
        for(long long  i=2;i*i<=n;i++)
        {///任何一个合数都至少有一个不超过根号n的素因子，复杂度为根号n
            if(n%i==0)///用公式
            {
                res=res-res/i;
                while(n%i==0)
                {
                    n=n/i;
                }
            }
        }
        if(n>1)///处理最后一个数
        {
            res=res-res/n;
        }
        return res;
    }///再此代码的基础上还可以用素数打表将其优化，请大家积极尝试
    
    int main()
    {
        long long  n;
        while(scanf("%lld",&n)!=EOF)
        {
            if(n==0)
                break;
            else
            {
                /*if(n==1)
                cout<<"0"<<endl;
                else*/
                printf("%lld\n",phi(n));
            }
        }
        return 0;
    }

Poj1284

公式：ans=phi(n-1);

代码实现：

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    int phi(int n)
    {
        int res=n;
        for(int i=2;i*i<=n;i++)
        {
            if(n%i==0)
            {
                res=res-res/i;
                while(n%i==0)
                {
                    n/=i;
                }
            }
        }
        if(n>1)
        {
            res=res-res/n;
        }
        return res;
    }
    
    int main()
    {
        int p;
        while(scanf("%d",&p)!=EOF)
        {
            cout<<phi(p-1)<<endl;
        }
        //cout << "Hello world!" << endl;
        return 0;
    }

Poj2478

公式：ans=∑phi(i);

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    const int maxn=1e6+5;
    
    int p[maxn];
    int phi()
    {
        for(int i=1;i<maxn;i++)
            p[i]=i;
        for(int i=2;i<maxn;i+=2)
        {
            p[i]/=2;
        }
        for(int i=3;i<maxn;i+=2)
        {
            if(p[i]==i)
            {
                for(int j=i;j<maxn;j+=i)
                {
                    p[j]=p[j]-p[j]/i;
                }
            }
        }
    }
    int main()
    {
        int n;
        long long ans;
        phi();
        while(scanf("%d",&n)!=EOF)
        {
            if(n==0) break;
            ans=0;
            for(int i=2;i<=n;i++)
            {
                ans+=p[i];
            }
            printf("%lld\n",ans);
        }
        return 0;
    }

Poj3090

公式：ans=3+2\*∑phi(i);

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    const int maxn=1e3+5;
    
    int p[maxn];
    int phi()
    {
        for(int i=1;i<maxn;i++)
            p[i]=i;
        for(int i=2;i<maxn;i+=2)
        {
            p[i]/=2;
        }
        for(int i=3;i<maxn;i+=2)
        {
            if(p[i]==i)
            {
                for(int j=i;j<maxn;j+=i)
                {
                    p[j]=p[j]-p[j]/i;
                }
            }
        }
    }
    
    int main()
    {
        int c;
        int n;
        int ans;
        phi();
        while(scanf("%d",&c)!=EOF)
        {
            for(int t=1;t<=c;t++)
            {
                scanf("%d",&n);
                ans=3;
                for(int i=2;i<=n;i++)
                {
                    ans+=2*p[i];
                }
                printf("%d %d %d\n",t,n,ans);
            }
        }
        return 0;
    }

Hdu1098

题目分析：分类讨论；与费马小定理结合起来

F(x)=5\*x^13+13\*x^5+k\*a\*x=(5\*x^12+13\*x^4+k\*a)\*x

1.若x能把65整除，则f(x)能把65整除。

2.若x能把5整除，则需要(5\*x^12+13\*x^4+k\*a)中(5\*x^12+k\*a)是13的倍数，由费马小定理，由于x是5的倍数，则有(x^(13-1)%13==1)，所以(5\*x^12%13=5)，所以只需要k\*a%13==8即可。

3.若x能把13整除，则需要(5\*x^12+13\*x^4+k\*a)中(13\*x^4+k\*a)是5的倍数，由费马小定理，由于x是13的倍数，则有(x^(5-1)%5==1)，所以(13\*x^4%5=3)，所以只需要k\*a%5==2即可。

综上，若x不是上述特殊值时，则需要F(x)=(5\*x^12+13\*x^4+k\*a)\*x被65整除，即同时满足上述2,3条件。

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    int main()
    {
        int k;
        int flag;
        while(scanf("%d",&k)!=EOF)
        {
            flag=0;
            for(int i=1;i<=65;i++)
            {
                if((k*i)%5==2 && (k*i)%13==8)
                {
                    flag=i;
                    break;
                }
            }
            if(flag)
            {
                printf("%d\n",flag);
            }
            else
            {
                printf("no\n");
            }
        }
        return 0;
    }

Hdu2824

打表求欧拉函数

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    const int maxn=3e6+5;
    
    int p[maxn];
    int phi()
    {
        for(int i=1;i<maxn;i++)
            p[i]=i;
        for(int i=2;i<maxn;i+=2)
        {
            p[i]/=2;
        }
        for(int i=3;i<maxn;i+=2)
        {
            if(p[i]==i)
            {
                for(int j=i;j<maxn;j+=i)
                {
                    p[j]=p[j]-p[j]/i;
                }
            }
        }
    }
    
    int main()
    {
        int a,b;
        long long ans;
        phi();
        while(scanf("%d%d",&a,&b)!=EOF)
        {
            ans=0;
            for(int i=a;i<=b;i++)
            {
                ans+=p[i];
            }
            printf("%lld\n",ans);
        }
        return 0;
    }

Poj3501

解释：a和b互素，则在a<b的情况下，a和b-a互素。则有所有互素的数的和为：phi(n)/2个n。

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    const int mod=1e9+7;
    
    long long phi(long long n)
    {
        long long res=n;
        for(long long i=2; i*i<=n; i++)
        {
            if(n%i==0)
            {
                res=res-res/i;
                while(n%i==0)
                {
                    n/=i;
                }
            }
        }
        if(n>1)
        {
            res=res-res/n;
        }
        return res;
    }
    
    int main()
    {
        long long n;
        long long ans;
        while(scanf("%lld",&n)!=EOF)
        {
            if(n==0) break;
            else
            {
                ans=n*(n-1)/2;
                ans=(ans-n*phi(n)/2)%mod;
                printf("%lld\n",ans);
            }
        }
        return 0;
    }

hdu4704

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    
    using namespace std;
    
    const int maxn=1e5+5;
    const long long mod=1e9+7;
    
    char str[maxn];
    long long a=0;
    void change()
    {
        a=0;
        int len=strlen(str);
        for(int i=0;i<len;i++)
        {
            a=(a*10+(str[i]-'0'))%(mod-1);
        }
        a--;
        a+=mod-1;
    }
    
    long long quick_mod(long long aa,long long b)
    {
        long long ans=1;
        while(b)
        {
            if(b&1)
            {
                ans=(ans*aa)%mod;
            }
            b>>=1;
            aa=(aa*aa)%mod;
        }
        return ans;
    }
    
    int main()
    {
    
        while(cin>>str)
        {
            change();
            cout<<quick_mod(2,a)<<endl;
        }
        return 0;
    }
    /*
    #include <iostream>
    #include <cstring>
    using namespace std;
    const int MAXN = 1e5+5;
    const int MOD = 1e9+7;
    typedef long long LL;
    LL quick_mod(LL a, LL b, LL m)
    {
        LL ans = 1;
        while(b)
        {
            if(b&1)
                ans = ans*a%m;
            b>>=1;
            a = a*a%m;
        }
        return ans;
    }
    LL GetMod(char st[])
    {
        LL ret = 0;
        int len = strlen(st);
        for(int i=0; i<len; i++)
            ret = (ret*10+(st[i]-'0')) % (MOD-1);
        ret--;
        return ret;
    }
    char str[MAXN];
    int main()
    {
        while(cin>>str)
        {
            LL tmp = GetMod(str);
            cout<<quick_mod(2, tmp, MOD)<<endl;
        }
        return 0;
    }*/