hdu1395

数论   欧拉函数

对于给出的每一个n

求最小正整数 x 满足 2^x mod n = 1

1、如果给出的n 是偶数或者 1 则一定无解

2、如果是奇数 首先根据欧拉定理 我们可知 phi(n)一定是满足要求的

然后答案一定是 phi( i ) 的因数

然后我们就可以 O(sqrt(phi(i))的时间内 枚举每个因数 然后快速幂验证就行了

 

1 #include 
     
        2 using namespace std ;  3  4 const double eps = 1e-8 ;  5 const int inf = 1e9 ;   6 int n,x,t,ans ;  7  8 inline int Phi(int n)   9 {10     int ans = n ; 11     for(int i=2,zz = int(sqrt(n)+eps);i<=zz;i++) 12     {13         if( n % i==0 ) 14             ans = ans - ans / i ; 15         while(n%i==0) n/=i ; 16     }17     if( n!=1 ) 18         ans = ans - ans/n ; 19     return ans ; 20 }21 22 inline int ksm(int base,int ind,int mod) 23 {24     int now = 0,b[32] ; 25     while(ind) 26     {27         b[++now] = ind&1 ; 28         ind = ind>>1 ; 29     } 30     int ans = 1 ; 31     for(int i=now;i>=1;i--) 32     {33         ans = ans * ans % mod ; 34         if(b[ i ]) ans = ans*base % mod ;  35     }36     return ans ; 37 }38 inline bool check(int x) { return ksm(2,x,n)==1 ; } 39 40 int main() 41 { 42      while(~scanf("%d",&n)) 43     {44         if(n%2==0||n==1) 45         {46             printf("2^? mod %d = 1\n",n) ; 47             continue ; 48         }49         t = Phi( n ) ; 50         ans = inf ;  51         for(int i=2,zz = int(sqrt(t)+eps);i<=zz;i++)     52         {53             if(t%i!=0) continue ;   54             if(check( i )) 55             {56                 ans = i ; 57                 break ; 58             }59             if(check( t/i )) 60                  if( t/i