2^x mod n = 1

25

2^? mod 2 = 12^4 mod 5 = 1

#include<iostream>#include<cstdio>#include<cmath>#include<cstring>using namespace std;const int Max = 1000010;int prime[Max], phi[Max]; //保存所有值的欧拉函数void fun() //求1到max所有值的欧拉函数{ int i,j;    prime[0] = prime[1] = 0;    for(i = 2;i <= Max; i ++)  prime[i]=1;    for(i = 2; i*i <= Max; i ++)        if(prime[i])           for(int j=i*i;j<=Max;j+=i)               prime[j]=0;    for(i=1;i<=Max;i++)         phi[i]=i;    for(i=2;i<=Max;i++)        if(prime[i])          for(j = i; j <= Max; j += i)              phi[j] = phi[j]/i * (i-1);}int Mod(int a, int b, int c) //快速幂取模  {    int ans = 1;    __int64 aa = a;    while(b)    {        if (b % 2)  ans = ans * aa % c;        aa = aa * aa % c;        b /= 2;    }    return ans;}int main(){//      freopen("a.txt","r",stdin);//      freopen("b.txt","w",stdout);    fun();    int a, n,i;    while(scanf("%d",&n)!=EOF)    {        int sn = (int)sqrt(phi[n]), ans = n;  //在1-sn之间枚举n的欧拉函数的因子        for(i = 1; i <= sn; i++) //在欧拉函数的所有因子中查找满足条件并且是最小的。        {            if (phi[n] % i == 0) //如果i是phi的因子  更新最小值            {                if (Mod(2, i, n) == 1 && ans > i)                    ans = i;                   if (Mod(2, phi[n] / i, n) == 1 && ans > phi[n] / i)                    ans = phi[n] / i;             }        }  if(ans==n) printf("2^? mod %d = 1\n",n);  else printf("2^%d mod %d = 1\n",ans,n);        //cout << ans << endl;    }    return 0;}