一些关于GCD的代码。。。。

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4  5 using namespace std; 6  7 typedef long long int LL; 8  9 LL EX_GCD(LL a,LL b,LL& x,LL& y)10 {11     if(b==0)12     {13         x=1;y=0;14         return a;15     }16     else17     {18         LL ret=EX_GCD(b,a%b,x,y);19         int t=x;20         x=y; y=t-a/b*y;21         return ret;22     }23 }24 25 LL inv(int a,int n)26 {27     LL x,y,d;28     d=EX_GCD(a,n,x,y);29     if(d==1)30         return (x%n+n)%n;31     else32         return -1;33 }34 35 LL euler_phi(int n)36 {37     LL ans=n;38     for(int i=2;i*i<=n;i++)39     {40         if(n%i==0)41         {42             ans=ans/i*(i-1);43             while(n%i==0) n/=i;44         }45     }46     if(n>1)47         ans=ans/n*(n-1);48     return ans;49 }50 51 LL phi[120];52 53 LL table_euler_phi(int n)54 {55     memset(phi,0,sizeof(phi));56     phi[1]=1;57     for(int i=2;i<=n;i++)58     {59         if(!phi[i])60         for(int j=i;j<=n;j+=i)61         {62             if(!phi[j]) phi[j]=j;63             phi[j]=phi[j]/i*(i-1);64         }65     }66 }67 68 int a[100],m[100];69 70 LL china(int n,int a[],int m[])71 {72     LL ans=0,x,y,M=1;73     for(int i=0;i