Problem about GCD

  1 #include<iostream>  2 #include<stdio.h>  3 #include<cstring>  4 #include<stdlib.h>  5 #include<time.h>  6 #include<math.h>  7 using namespace std;  8 typedef __int64 LL;  9 const int maxn = 1e6+1; 10 int prime[maxn],len; 11 bool s[maxn]; 12  13 void init() 14 { 15     int i,j; 16     len = 0; 17     memset(s,true,sizeof(s)); 18     s[1] = false; 19     for(i=2;i<maxn;i++) 20     { 21         if(s[i] == false) continue; 22         prime[++len] = i; 23         for(j=i*2;j<maxn;j=j+i) 24             s[j] = false; 25     } 26 } 27 //**************************************************************** 28 // Miller_Rabin 算法进行素数测试 29 //速度快，而且可以判断 <2^63的数 30 //**************************************************************** 31 const int S=20;//随机算法判定次数，S越大，判错概率越小 32 LL mult_mod(LL a,LL b,LL mod) //(a*b)%c a,b,c<2^63 33 { 34     a%=mod; 35     b%=mod; 36     LL ans=0; 37     while(b) 38     { 39         if(b&1) 40         { 41             ans=ans+a; 42             if(ans>=mod) 43             ans=ans-mod; 44         } 45         a=a<<1; 46         if(a>=mod) a=a-mod; 47         b=b>>1; 48     } 49     return ans; 50 } 51 LL pow_mod(LL a,LL b,LL mod) // a^b%mod 52 { 53     LL ans=1; 54     a=a%mod; 55     while(b) 56     { 57         if(b&1) 58         { 59             ans=mult_mod(ans,a,mod); 60         } 61         a=mult_mod(a,a,mod); 62         b=b>>1; 63     } 64     return ans; 65 } 66  67 //以a为基,n-1=x*2^t      a^(n-1)=1(mod n)  验证n是不是合数 68 //一定是合数返回true,不一定返回false 69  70 bool check(LL a,LL n,LL x,LL t) 71 { 72     LL ret=pow_mod(a,x,n); 73     LL last=ret; 74     for(int i=1;i<=t;i++) 75     { 76         ret=mult_mod(ret,ret,n); 77         if(ret==1 && last!=1 && last!=n-1) return true;//合数 78         last=ret; 79     } 80     if(ret!=1) return true; 81     else return false; 82 } 83  84 // Miller_Rabin()算法素数判定 85 //是素数返回true.(可能是伪素数，但概率极小) 86 //合数返回false; 87  88 bool Miller_Rabin(LL n) 89 { 90     if(n<2)return false; 91     if(n==2) return true; 92     if( (n&1)==0) return false;//偶数 93     LL x=n-1; 94     LL t=0; 95     while( (x&1)==0 ) { x>>=1;t++;} 96     for(int i=0;i<S;i++) 97     { 98         LL a=rand()%(n-1)+1;//rand()需要stdlib.h头文件 99         if(check(a,n,x,t))100         return false;//合数101     }102     return true;103 }104 bool Euler(LL n)105 {106     LL i , knum = 0;107     for(i=1;prime[i]<=n&&i<=len;i++)108     {109         if(n%prime[i]==0)110         {111             while(n%prime[i]==0)112                 n=n/prime[i];113             knum++;114         }115         if(knum>=2) break;116     }117     if(knum == 1 && n==1) return true;118     /**此处为n == 1 不是n == 0**/119     return false;120 }121 void solve(LL n,LL m)122 {123     if( (m<=1000000 && s[m] == true) || Miller_Rabin(m) == true)124     {125         printf("%I64d\n",n-1);126         return;127     }128     LL k = (LL)sqrt(m*1.0);129     if(k * k == m && Miller_Rabin(k) == true)130     {131         printf("%I64d\n",n-1);132         return;133     }134     if(Euler(m)==true)135     {136         printf("%I64d\n",n-1);137         return;138     }139     printf("1\n");140 }141 int main()142 {143     init();144     LL n , m;145     while(scanf("%I64d",&n)>0)146     {147         if(n==-1) break;148         if(n<=5){149             printf("%I64d\n",n-1);150             continue;151         }152         m = n;153         if( (m&1) == 0)154         {155             m = m /2;156             if((m&1)==0)157             {158                 printf("1\n");159                 continue;160             }161         }162         solve(n,m);163     }164     return 0;165 }