Hdu 1395 2^x mod n = 1 (欧拉定理分解素因数)

阳光穿透心脏的1/2处 2022-09-19 12:11 215阅读 0赞

先吐槽一下：考完试后第一天实验室就断网，简直不可思议。

题意：给出n,找出最小的x使其满足2^x mod n = 1

思路：欧拉定理（费马小定理的欧拉推广）可得如果n为1或2的倍数则无解，n为大于1的奇数时一定有解。由于测试数据很水，之后暴力枚举就可以了，据说测试数据中n不大于5000。

之前做时直接暴力解决，这回决定使用一般的思路

以下内容参考了：http://blog.csdn.net/xieshimao/article/details/6688618

把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的一个因子。

做完这题后去看了一下以前瞄过一眼的“原根和指标”，这回稍微看懂一些了，但还不是很明白，过段时间消化一下再继续学习吧。

#include <cstdio>
    
    const int N=5005;
    int prime[N],np=0;
    int pnum[N],num;
    bool tag[N];
    
    void Prime ()
    {//共np个素数,保存在prime[0]~prime[np-1]
        for (int i=2;i<N;i++) if (tag[i] == false)
        {
            prime[np++]=i;
            for (int j=i+i;j<N;j+=i)
                tag[j]=true;
        }
    }
    
    int Euler (int n)
    {
        int i,ans=n;
        for (i=2;i*i<=n;i++) if(n%i==0)
        {
            ans=ans/i*(i-1);
            while (n%i==0) n/=i;
        }
        if (n>1) ans=ans/n*(n-1);
        return ans;
    }
    
    __int64 POW (__int64 s,__int64 index,__int64 mod)
    {
        __int64 ans=1;
        s%=mod;
        while (index>=1)
        {
            if ((index&1)==1)   //奇数
                ans=(ans*s)%mod;
            index>>=1;
            s=s*s%mod;
        }
        return ans;
    }
    
    void split (__int64 n) //pnum数组保存分出的素因子
    {
        num=0;//注意int相乘有可能会超int可表示的范围
        for (int i=0;i<np && (__int64)prime[i]*prime[i]<=n;i++)
        {
            if (n%prime[i]==0)
            {
                pnum[num]=prime[i];
                while (n%prime[i]==0)
                {
                   n/=prime[i];
                }
                num++;
            }
        }
        if (n>1) pnum[num++]=n;
    }
    
    int Deal (int n,int mod)
    {
    	bool flag=true;
    	int ans=n;
    	while (flag)  //一次只分出一个素因子的一次方
    	{
    		flag=false;
    		split(n);
    		for (int i=0;i<num;i++)  
            {
                if (POW(2,n/pnum[i],mod)==1)  
                {
                    flag=true;
                    if (n/pnum[i]<ans)
    					ans=n/pnum[i];
                }
            }
            n=ans;
        }
    	return ans;
    }
    
    int main ()
    {
        int n;
        Prime ();
        while (~scanf("%d",&n))
        {
            if (n==1 || n%2==0)
            {
                printf("2^? mod %d = 1\n",n);
                continue;
            }
            int phi=Euler(n);
            printf("2^%d mod %d = 1\n",Deal (phi,n),n);
        }
    	return 0;
    }