HDU 1395(欧拉定理)

绝地灬酷狼 2022-09-20 12:49 169阅读 0赞

欧拉φ函数的值 　通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。 (注意：每种质因数只一个。比如12=2\*2\*3  欧拉公式  
那么φ（12）=12\*（1-1/2）\*(1-1/3)=4  
若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。  
设n为正整数，以 φ(n)表示不超过n且与n互  
素的正整数的个数，称为n的欧拉函数值，这里函数  
φ：N→N，n→φ(n)称为欧拉函数。  
欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。  
特殊性质：当n为奇数时，φ(2n)=φ(n), 证明与上述类似。

求欧拉函数的c语言函数:

int eular(int n) {  
    	int ret=1,i;   
    	for(i=2;i*i<=n;i++)     
    		if(n%i==0)     
    		{      
    			n/=i,ret*=i-1;      
    			while(n%i==0)     
    				n/=i,ret*=i;    
    		}  
    		if(n>1)     
    			ret*=n-1, cout << n << endl;
    		return ret; 
    }

求欧拉函数的c++程序：

#include <cstdio> 
    #include <cstdlib>   
    using namespace std;   
    #define N 10000000   
    int main(int argc, const char *argv[]) 
    {     
    	int *phi;     
    	char *prime;     
    	prime = (char*)malloc((N + 1) * sizeof(char));     
    	prime[0] = prime[1] = 0;     
    	for(int i = 2; i <= N; i++)         
    		prime[i] = 1;     
    	for(int i = 2; i * i <= N; i++)         
    		if(prime[i])             
    			for(int j = i * i; j <= N; j += i)                 
    				prime[j] = 0;     //这段求出了N内的所有素数     
    	phi = (int*)malloc((N + 1) * sizeof(int));     
    	for(int i = 1; i <= N; i++)         
    		phi[i] = i;     
    	for(int i = 2; i <= N; i++)         
    		if(prime[i])             
    			for(int j = i; j <= N; j += i)                 
    				phi[j] = phi[j] / i * (i - 1); //此处注意先/i再*（i-1)，否则范围较大时会溢出     
    	return 0; 
    } //这段求出了N内所有数的欧拉函数值

当a，n互质时，a^φ（n）=1（mod n）.

这道题目可以用暴力解决：

#include <cstdio>
    
    void main()
    {
        int n, x, round;
        while (scanf("%d", &n) != EOF)
        {
            if (n % 2 == 0 || n == 1)
            {
                printf("2^? mod %d = 1\n", n);
            }
            else
            {
                x = 1, round = 2;
                while (round != 1)
                {
                    round = round * 2 % n;
                    ++x;
                }
                printf("2^%d mod %d = 1\n", x, n);
            }
        }
    }

也可以用欧拉定理：

下面提供两个用欧拉定理解决的程序：

#include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    #define LL __int64
    LL t,e[1000];
    LL mod;
    LL euler_phi(LL n)//欧拉函数
    {
        LL m=sqrt(n+0.5);
        LL ans=n,i;
        for(i=2;i<=m;i++)
        {
            if(n%i==0)
            {
                ans=ans/i*(i-1);
                while(n%i==0)n=n/i;
            }
        }
        if(n>1)ans=ans/n*(n-1);
        return ans;
    }
    void find(LL n)
    {
        LL i;
        e[t++]=n;
        for(i=2;i*i<=n;i++)
        {
            if(n%i==0)
            {
                if(i*i==n)
                    e[t++]=i;
                else
                {
                    e[t++]=i;
                    e[t++]=n/i;
                }
            }
        }
    }
    LL pows(LL a,LL b)
    {
        LL s=1;
        while(b)
        {
            if(b&1)
                s=(s*a)%mod;
            a=(a*a)%mod;
            b=b>>1;
        }
        return s;
    }
    int main()
    {
        LL n;
        while(cin>>n)
        {
            if(n%2==0||n==1)
                cout<<"2^? mod "<<n<<" = 1"<<endl;
            else
            {
                LL m,ans,i,s=2;
                /*for(i=2;;i++)//直接暴力的方法
                {
                    s=(s*2)%n;
                    if(s==1)
                        break;
                }
                ans=i;*/
                m=euler_phi(n);
                t=0;
                find(m);
                sort(e,e+t);
                mod=n;
                for(i=0;i<t;i++)
                {
                    if(pows(2,e[i])==1)
                    {
                        ans=e[i];
                        break;
                    }
                }
                cout<<"2^"<<ans<<" mod "<<n<<" = 1"<<endl;
            }
        }
        return 0;
    }
    /*
        这题数据很水，可以直接暴力出来。
        我要讲的使用定理求解这道题：
        本题很容易发现n为偶数或者0时无解。所以2和n必定互质
        欧拉定理:a^(euler_phi(n))≡1(mod n),(a,n互质)
        其中euler_phi为欧拉函数，计算不超过n且与n互质的个数。求法是n*∏(pi-1)/pi,pi为n的质因子
        
        m=euler_phi(n);
        所以a^m%mod=1,不过m不一定是最小循环，但m是一个循环，则最小循环不定时m的一个因子，因而找出所有m的因子，暴力
        搜索下就OK了
    */

/*做法要利用这样几个定理：
    第一个是a^phi(m)%m=1
    这个等式在m和a互质的时候一定成立
    在这个题目中，因为a=2
    所以m与a不互质，除非m为偶数
    当然m=1的时候需要特殊处理下，这些都是小问题。
    现在这个问题明了了，即在m为奇数(大于1)的时候一定有解。
    那么就有人萌生了直接暴力的方法。当然对于这个题，直接暴力是可以的，我最先开始也是这样过的
    但是今天重新做了一下这个题我仔细的思考了一下，发现果然有更加巧妙的方法来解决该类问题。
    首先说暴力的缺点吧，大多数情况暴力其实还是非常快的，但是如果当m为一个非常大的质数，那么问题就严重了。因为质数的欧拉函数就是质数-1
    那么也就是说，最坏情况下，我们可能要枚举很多次才能找到一个解
    那么更为高效的方法是：把m的欧拉函数值，假设值为phi进行质因数分解
    然后依次枚举phi的每一个因子，同时判断这个因子x是否满足2^x%m==1，不断更新一个最小值，最后得到答案。
    那么为什么这样做就是对的呢？
    首先需要知道：
    a^x%m==1满足这个方程的最小x称为a对模m的指数。我们记做ordm(a)，如果ordm(a)==phi(m)则我们称a为模m的原根
    有：a^X%m==1    <-===->    ordm(a)整除X
    根据以上所说：a^phi(m)=1成立，那么phi(m)%ordm(a)==0也是成立的
    所以ordm(a)就是phi的一个因子
    所以分解phi然后枚举phi的因子的做法是正确的（恩，是有科学依据的。。哈哈）
    */
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<iostream>
    #define inf 99999999
    #define maxn 1000000
    
    using namespace std;
    typedef __int64 ll;
    
    bool flag[maxn];
    ll prime[maxn];
    
    void init()
    {
    	ll i,j,num=0;
    	for(i=2;i<maxn;i++)
    	{
    		if(!flag[i])
    		{
    			prime[num++]=i;
    			for(j=i*i;j<maxn;j=j+i)
    				flag[j]=true;
    		}
    	}
    }
    
    ll eular(ll n)
    {
    	ll i,res=1;
    	for(i=2;i*i<=n;i++)
    	{
    		if(n%i==0)
    		{
    			res=res*(i-1);
    			n=n/i;
    			while(n%i==0)
    			{
    				res=res*i;
    				n=n/i;
    			}
    		}
    		if(n==1)
    			break;
    	}
    	if(n>1)
    		res=res*(n-1);
    	return res;
    }
    
    ll exmod(ll a,ll b,ll n)
    {
    	ll ret=1;
    	for(;b;b>>=1,a=a*a%n)
    		if(b&1)
    			ret=ret*a%n;
    	return ret;
    }
    
    ll solve(ll n,ll fac[])
    {
    	ll i,num=0;
    	for(i=0;prime[i]*prime[i]<=n;i++)
    	{
    		if(n%prime[i]==0)
    		{
    			n=n/prime[i];
    			fac[num++]=prime[i];
    			while(n%prime[i]==0)
    			{
    				n=n/prime[i];
    				fac[num++]=prime[i];
    			}
    		}
    		if(n==1)
    			break;
    	}
    	if(n>1)
    		fac[num++]=n;
    	return num;
    }
    
    void getans(ll n,ll mod)
    {
    	ll fac[100],num,ans=n,i;
    	bool loop=true;
    	while(loop)
    	{
    		loop=false;
    		num=solve(n,fac);
    		for(i=0;i<num;i++)
    		{
    			if(exmod(2,n/fac[i],mod)==1)
    			{
    				loop=true;
    				if(n/fac[i]<ans)
    					ans=n/fac[i];
    			}
    		}
    		n=ans;
    	}
    	printf("2^%I64d mod %I64d = 1\n",ans,mod);
    }
    
    int main()
    {
    	ll n,phi;
    	init();
    	while(scanf("%I64d",&n)!=EOF)
    	{
    		if(n%2==0||n==1)
    		{
    			printf("2^? mod %I64d = 1\n",n);
    			continue;
    		}
    		phi=eular(n);
    		getans(phi,n);
    	}
    	return 0;
    }