数论基础代码合集

以你之姓@ 2023-07-02 04:23 156阅读 0赞

# **欧几里德** #

#include<iostream>
    using namespace std;
    int hcf(int a,int b)      
    {
        int r=0;
        while(b!=0)
        {
            r=a%b;
            a=b;
            b=r;
        }
        return(a);
    }
    lcd(int u,int v,int h) //u=a，v=b，h为最小公约数=hcf(a,b);
    {
        return(u*v/h);
    }
    int main()
    {
           int a,b,x,y;
           cin>>a>>b;
           x=hcf(a,b);
           y=lcd(a,b,x);
           cout<<x<<" "<<y<<endl;
           return 0;
    }

# **扩展欧几里德** #

#include <iostream>
    using namespace std;
    __int64 ext_euclid(__int64 a,__int64 b, __int64 &x, __int64 &y)
    {
        int t;
           __int64 d;
        if (b==0) {x=1;y=0;return a;}
        d=ext_euclid(b,a %b,x,y);
        t=x;
        x=y;
        y=t-a/b*y;
        return d;
    }
    void modular_equation(__int64 a,__int64 b,__int64 c)//ax = b(mod n)
    {
        __int64 d;
        __int64 x,y;
        d = ext_euclid(a,b,x,y);
        if ( c % d != 0 )
                  printf("No answer\n");
        else
        {
                  x = (x * c/d) % b ;// 第一次求出的x ;
                  __int64 t = b/d;
                  x = (x%t + t)%t;
                  printf("%I64d\n",x);//最小的正数的值
                  for (int i=0;i<d;i++)
                         printf("The %dth answer is : %ld\n",i+1,(x+i*(b/d))%b); //所有的正数值
        }
    }
    /*
    
    函数返回值为gcd(a,b),并顺带解出ax+by=gcd(a,b)的一个解x,y,
    
    
    
      对于不定方程ax+by=c的通解为：
    
      x=x*c/d+b/d*t
    
      y=y*c/d+a/d*t
    
    当c%gcd(a,b)!=0时,不定方程无解.*/

# **中国剩余定理** #

#include <iostream>
    using namespace  std;
     int ext_euclid(int a,int b,int &x,int &y)  //求gcd(a,b)=ax+by
    {
        int t,d;
        if (b==0) {x=1;y=0;return a;}
        d=ext_euclid(b,a %b,x,y);
        t=x;
        x=y;
        y=t-a/b*y;
        return d;
    }
    
    int China(int W[],int B[],int k)   //W为按多少排列，B为剩余个数   W>B  K为组数
    {
        int i;
        int d,x,y,a=0,m,n=1;
        for (i = 0;i<k;i++)
            n *= W[i];
        for (i=0;i<k;i++)
           {
                  m=n/W[i];
            d=ext_euclid(W[i],m,x,y);
            a=(a+y*m*B[i])%n;
           }
        if (a>0
                  return a;
        else
                  return(a+n);
    }
    
    int main()
    
    {
    
           int B[100],W[100];                                求
    
           int k ;                                           a = 2( mod 5 )
    
           cin >> k ;                                        a = 3( mod 13)
    
           for(int i = 0 ; i < k ;i++)                            的解
    
           {                                               2
    
                  cin >> W[i];                                  5 2
    
                  cin >> B[i];                                   13 3 
    
           }                                               输出 42
    
           cout<<China(W,B,k)<<endl;
    
           return 0;
    
    }

# **欧拉函数** #

# **求小于****n****的所有欧拉数** #

#include <iostream>
    
    using namespace std;
    
    int phi[1000];     //数组中储存每个数的欧拉数
    
    
    
    void genPhi(int n)//求出比n小的每一个数的欧拉数(n-1的)
    
    {
    
           int i, j, pNum = 0 ;
    
           memset(phi, 0, sizeof(phi)) ;
    
           phi[1] = 1 ;
    
           for(i = 2; i < n; i++)
    
           {
    
                  if(!phi[i])
    
                  {
    
                         for(j = i; j < n; j += i)
    
                         {
    
                                if(!phi[j])
    
                                       phi[j] = j;
    
                                phi[j] = phi[j] / i * (i - 1);
    
                         }
    
                  }
    
           }
    
    }

# **求****n****的欧拉数** #

int eular(int n)
    
    {
    
           int ret=1,i;
    
           for (i=2;i*i<=n;i++)
    
                  if (n%i==0)
    
                  {
    
                         n/=i,ret*=i-1;
    
                         while (n%i==0)
    
                                n/=i,ret*=i;
    
                  }
    
                  if (n>1)
    
                         ret*=n-1;
    
                  return ret;    //n的欧拉数
    
    }

# **行列式计算** #

#include <iostream>
    
    using namespace std;
    
    int js(int s[100][100],int n)
    
    {
    
        int z,j,k,r,total=0;
    
        int b[100][100];  /*b[N][N]用于存放，在矩阵s[N][N]中元素s[0]的余子式*/
    
        if(n>2)
    
           {
    
            for(z=0;z<n;z++)
    
                  {
    
                for(j=0;j<n-1;j++)
    
                  for(k=0;k<n-1;k++)
    
                         if(k>=z)
    
                                 b[j][k]=s[j+1][k+1]; 
    
                         else
    
                                b[j][k]=s[j+1][k];
    
                         if(z%2==0)
    
                                r=s[0][z]*js(b,n-1); /*递归调用*/
    
                         else
    
                                r=(-1)*s[0][z]*js(b,n-1);
    
                         total=total+r;
    
                  }
    
           }
    
        else if(n==2)
    
                  total=s[0][0]*s[1][1]-s[0][1]*s[1][0];
    
        return total;
    
    }

# **排列** #

long A(long n,long m)   //n>m
    
    {
    
        long a=1;
    
        while(m!=0)  {a*=n;n--;m--;}
    
        return a;
    
    }

# **组合** #

long C(long n,long m)     //n>m
    
    {
    
        long i,c=1;
    
        i=m;
    
        while(i!=0)   {c*=n;n--;i--;}
    
    while(m!=0)  {c/=m;m--;}
    
    return c;
    
    }

# **大数乘大数** #

#include <iostream>
    #include <string>
    using namespace std;
    char a[1000],b[1000],s[10000];
    void mult(char a[],char b[],char s[])     //a被乘数，b乘数，s为积
    {
        int i,j,k=0,alen,blen,sum=0,res[65][65]={0},flag=0;
        char result[65];
        alen=strlen(a);blen=strlen(b);
        for (i=0;i<alen;i++)
        for (j=0;j<blen;j++) res[i][j]=(a[i]-'0')*(b[j]-'0');
        for (i=alen-1;i>=0;i--)
            {
                for (j=blen-1;j>=0;j--) sum=sum+res[i+blen-j-1][j];
                result[k]=sum%10;
                k=k+1;
                sum=sum/10;
            }
        for (i=blen-2;i>=0;i--)
            {
                for (j=0;j<=i;j++) sum=sum+res[i-j][j];
                result[k]=sum%10;
                k=k+1;
                sum=sum/10;
            }
        if (sum!=0) {result[k]=sum;k=k+1;}
        for (i=0;i<k;i++) result[i]+='0';
        for (i=k-1;i>=0;i--) s[i]=result[k-1-i];
        s[k]='\0';
        while(1)
            {
            if (strlen(s)!=strlen(a)&&s[0]=='0')
                strcpy(s,s+1);
            else
                break;
            }
    }
    
    int main()
    
    {
    
           cin>>a>>b;
    
           mult(a,b,s);
    
           cout<<s<<endl;
    
           return 0;}

# **大数乘小数** #

#include <iostream>
    
    using namespace std;
    
    char a[100],t[1000];
    
    void mult(char c[],int m,char t[])  // c为大数,m<=10,t为积
    
    {
    
        int i,l,k,flag,add=0;
    
        char s[100];
    
        l=strlen(c);
    
        for (i=0;i<l;i++)
    
            s[l-i-1]=c[i]-'0';
    
        for (i=0;i<l;i++)
    
           {
    
                  k=s[i]*m+add;
    
                  if (k>=10)
    
                  {
    
                         s[i]=k%10;add=k/10;flag=1;
    
                  }
    
                  else
    
                  {
    
                         s[i]=k;flag=0;add=0;
    
                  }
    
           }
    
        if (flag)
    
           {
    
                  l=i+1;s[i]=add;
    
           }
    
           else
    
                  l=i;
    
        for (i=0;i<l;i++)
    
            t[l-1-i]=s[i]+'0';
    
        t[l]='\0';
    
    }
    
    int main()
    
    {
    
           int i;
    
           cin>>a>>i;
    
           mult(a,i,t);
    
           cout<<t<<endl;
    
           return 0;
    
    }

# **大数加法** #

#include <iostream>
    
    #include <string>
    
    using namespace std;
    
    char a[1000],b[1000],s[10000];
    
    void add(char a[],char b[],char s[])//a被加数，b加数，s和
    
    {
    
        int i,j,k,up,x,y,z,l;
    
        char *c;
    
        if (strlen(a)>strlen(b)) l=strlen(a)+2; else l=strlen(b)+2;
    
        c=(char *) malloc(l*sizeof(char));
    
        i=strlen(a)-1;
    
        j=strlen(b)-1;
    
        k=0;up=0;
    
        while(i>=0||j>=0)
    
           {
    
                  if(i<0) x='0'; else x=a[i];
    
                  if(j<0) y='0'; else y=b[j];
    
                  z=x-'0'+y-'0';
    
                  if(up) z+=1;
    
                  if(z>9) {up=1;z%=10;} else up=0;
    
                  c[k++]=z+'0';
    
                  i--;j--;
    
           }
    
        if(up) c[k++]='1';
    
        i=0;
    
        c[k]='\0';
    
        for(k-=1;k>=0;k--)
    
            s[i++]=c[k];
    
        s[i]='\0';
    
    }
    
    int main()
    
    {
    
           cin>>a>>b;
    
           add(a,b,s);
    
           cout<<s<<endl;
    
           return 0;
    
    }

# **大数减法** #

#include <iostream>
    
    using namespace std;
    
    char a[1000],b[1000],s[10000];
    
    void sub(char a[],char b[],char s[])
    
    {
    
        int i,l2,l1,k;
    
        l2=strlen(b);l1=strlen(a);
    
        s[l1]='\0';l1--;
    
        for (i=l2-1;i>=0;i--,l1--)
    
            {
    
            if (a[l1]-b[i]>=0)
    
                s[l1]=a[l1]-b[i]+'0';
    
            else
    
                {
    
                s[l1]=10+a[l1]-b[i]+'0';
    
                a[l1-1]=b[l1-1]-1;
    
                }
    
            }
    
        k=l1;
    
        while(a[k]<0) {a[k]+=10;a[k-1]-=1;k--;}
    
        while(l1>=0) {s[l1]=a[l1];l1--;}
    
    loop:
    
        if (s[0]=='0')
    
            {
    
            l1=strlen(a);
    
            for (i=0;i<l1-1;i++) s[i]=s[i+1];
    
            s[l1-1]='\0';
    
            goto loop;
    
            }
    
        if (strlen(s)==0) {s[0]='0';s[1]='\0';}
    
    }
    
    
    
    int main()
    
    {
    
           cin>>a>>b;
    
           sub(a,b,s);
    
           cout<<s<<endl;
    
           return 0;
    
    }

# **大数阶乘** #

#include <iostream>
    
    #include <cmath>
    
    using namespace std;
    
    long a[10000];
    
    int factorial(int n)         //n为所求阶乘的n!的n
    
    {
    
           int i,j,c,m=0,w;
    
           a[0]=1;
    
           for(i=1;i<=n;i++)
    
       {
    
                  c=0;
    
                  for(j=0;j<=m;j++)
    
           {
    
                         a[j]=a[j]*i+c;
    
                         c=a[j]/10000;
    
                         a[j]=a[j]%10000;
    
               }
    
                  if(c>0) {m++;a[m]=c;}
    
           }
    
           w=m*4+log10(a[m])+1;
    
           printf("%ld",a[m]); //        输出
    
           for(i=m-1;i>=0;i--) //
    
                  printf("%4.4ld",a[i]);//
    
           printf("\n");
    
           return w;            //返回值为阶乘的位数
    
    }

**储存方法很巧，每一个****a\[i\]****中存四位，不足四位在前加****0****补齐**

# **大数求余** #

int mod(int B)     //A为大数，B为小数
    
    {
    
           int i = 0,r = 0;
    
           while( A[i] != '\0' )
    
           {
    
                  r=(r*10+A[i++]-'0')%B;
    
           }
    
        return r ;    //r为余数
    
    }

# **高精度任意进制转换** #

#include <iostream>
    
    #include <string>
    
    using namespace std;
    
    char s[1000],s2[1000];   // s[]:原进制数字，用字符串表示，s2[]:转换结果，用字符串表示
    
    long d1,d2;   // d1:原进制数，d2:需要转换到的进制数
    
    void conversion(char s[],char s2[],long d1,long d2)
    
    {
    
        long i,j,t,num;
    
        char c;
    
        num=0;
    
        for (i=0;s[i]!='\0';i++)
    
           {
    
            if (s[i]<='9'&&s[i]>='0') t=s[i]-'0'; else t=s[i]-'A'+10;
    
            num=num*d1+t;
    
           }
    
        i=0;
    
        while(1)
    
           {
    
            t=num%d2;
    
            if (t<=9) s2[i]=t+'0'; else s2[i]=t+'A'-10;
    
            num/=d2;
    
            if (num==0) break;
    
            i++;
    
           }
    
        for (j=0;j<=i/2;j++)
    
           {c=s2[j];s2[j]=s2[i-j];s2[i-j]=c;}
    
        s2[i+1]='\0';
    
    }
    
    int main()
    
    {
    
           while (1)
    
           {
    
                  cin>>s>>d1>>d2;
    
                  conversion(s,s2,d1,d2);
    
                  cout<<s2<<endl;
    
           }
    
           return 0;
    
    }

**判断一个数是否素数**

**\#include <iostream>//****基本方法，****n****为所求数，返回****1****位素数，****0****为合数**

**\#include <cmath>**

**using namespace std;**

**int comp(int n)\{**

**int i,flag=1;**

**for (i=2;i<=sqrt(n);i++)**

**if (n%i==0) \{flag=0;break;\}**

**if (flag==1) return 1; else return 0;\}**

**素数表**

int prime(int a[],int n)            //小于n的素数
    
    {   int i,j,k,x,num,*b;
    
        n++;
    
        n/=2;
    
        b=(int *)malloc(sizeof(int)*(n+1)*2);
    
        a[0]=2;a[1]=3;num=2;
    
        for(i=1;i<=2*n;i++)
    
            b[i]=0;
    
        for(i=3;i<=n;i+=3)
    
            for(j=0;j<2;j++)
    
                {
    
                x=2*(i+j)-1;
    
                while(b[x]==0)
    
                    {
    
                    a[num++]=x;
    
                    for(k=x;k<=2*n;k+=x)
    
                        b[k]=1;
    
                    }
    
                }
    
        return num; }                //小于n的素数的个数}
    
    bool flag[1000000];
    
    void prime(int M)               //01表
    
    {     int i , j;
    
           int sq = sqrt(double(M));     
    
           for(i = 0 ;i < M ;i ++)
    
                  flag[i] = true;    
    
           flag[1] = false;   flag[0] = false;
    
           for(i = 2 ;i <= sq ;i++)
    
                  if(flag[i])
    
                  {
    
                         for(j = i*i ;j < M ;j += i)
    
                                flag[j] = false;
    
                  }
    
    }

**Miller\_Rabin****随机素数测试算法**

**说明：这种算法可以快速地测试一个数是否**

**满足素数的必要条件，但不是充分条件。不**

**过也可以用它来测试素数，出错概率很小，**

**对于任意奇数****n>2****和正整数****s,****该算法出错概率**

**至多为****2^(-s)****，因此，增大****s****可以减小出错概**

**率，一般取****s=50****就足够了。**

#include<iostream>
    
    #include <cmath>
    
    using namespace std;
    
    int Witness(int a, int n)  
    
    {  
    
           int i, d = 1, x;  
    
           for (i = ceil( log( (float) n - 1 ) / log(2.0) ) - 1; i >= 0; i--)    
    
           {  
    
                  x = d;  
    
                  d = (d * d) % n;  
    
                  if ( (d == 1) && (x != 1) && (x != n-1) )
    
                         return 1;  
    
                  if ( ( (n - 1) & ( 1<<i ) ) >0 )
    
                         d = (d * a) % n;  
    
           }  
    
           return (d == 1 ? 0 : 1);          
    
    }  
    
    
    
    int Miller_Rabin(int n, int s)  
    
    {  
    
           int j, a;  
    
           for (j = 0; j < s; j++)  
    
           {    
    
                  a = rand() * (n - 2) / RAND_MAX + 1;  
    
                  if (Witness(a, n))
    
                         return 0;  
    
           }  
    
           return 1;        
    
    }  
    
    int main()
    
    {
    
           int x;
    
           cin>>x;
    
           cout<<Miller_Rabin(x , 50)<<endl;
    
           return 0;
    
    }

# **整数拆分不可重复** #

#include <iostream>
    
    #include <memory>
    
    using namespace std;
    
    const int MAX = 500;
    
    long long data[MAX][MAX];
    
    int main()
    
    {
    
           int i,j;
    
           memset(data, 0, sizeof(int)*MAX);
    
           for(i = 0; i < MAX; i++)
    
                  data[0][i] = 0;
    
           for(i = 0; i < MAX; i++)
    
           {
    
                  for(j = 0; j < MAX; j++)
    
                  {
    
                         int sum = j*(j+1)/2;
    
                         if(i > sum) data[i][j] = 0;
    
                         else if(i == sum) data[i][j] = 1;
    
                         else
    
                         {
    
                                if(i == j) data[i][j] = 1 + data[i][j-1];
    
                                else if(i < j) data[i][j] = data[i][i];
    
                                else data[i][j] = data[i-j][j-1] + data[i][j-1];
    
                         }
    
                  }
    
           }
    
           int n;
    
           while(cin >> n)
    
                  cout << data[n][n] << endl;
    
           return 0;
    
    }
    
    整数拆分积最大
    
    int data[100];
    
    void main(int n;)
    
    {      int k = 2;
    
           for(; n >= k; n-=k,k++)
    
                  data[k] = k;
    
           for(int i = k-1; i >= 2 && n; i--, n--)
    
                  data[i]++;
    
           data[k-1] += n;
    
           for(int j = 2; j < k; j++)
    
                  cout << data[j] << " ";
    
           cout << endl; }

# **整数的无序拆分（可重复）** #

#include <iostream>       //求出可分解个数
    
    #include <memory>
    
    using namespace std;
    
    const int MAX = 600;
    
    long long data[MAX][MAX];
    
    int main()
    
    {
    
           int i,j;
    
           memset(data, 0, sizeof(int)*MAX);
    
           for(j = 0; j < MAX; j++)
    
                  data[0][j] = 0;
    
           for(i = 1; i < MAX; i++)
    
           {
    
                  for(j = 1; j < MAX; j++)
    
                  {
    
                         if(i == j)
    
                                data[i][j] = data[i][j-1]+1;
    
                         else if(i < j)
    
                                data[i][j] = data[i][i];
    
                         else
    
                                data[i][j] = data[i][j-1]+data[i-j][j];
    
                  }
    
           }     
    
           int n;
    
           while(cin >> n)
    
                  cout << data[n][n] << endl;
    
           return 0;
    
    }

# **整数的无序拆分（可重复）** #

#include <iostream>   //列出分解情况
    
    #include <memory>
    
    using namespace std;
    
    const int MAX = 300;
    
    int data[MAX];
    
    int main()
    
    {
    
           int i,n;
    
           cin >> n;
    
           for(i = 0; i < n; i++)
    
           {
    
                  data[i] = 1;
    
                  printf("1");
    
           }
    
           printf("\n");
    
           int size = n;
    
           while(size > 1)
    
           {
    
                  int t, p, r;
    
                  t = data[size-1] + data[size-2];
    
                  p = t / (data[size-2]+1);
    
                  r = t % (data[size-2]+1);
    
                 
    
                  t = data[size-2]+1;
    
                  i = size - 2;
    
                  size = size - 2 + p;
    
                  for(; i < size; i++)
    
                         data[i] = t;
    
                  data[size-1] += r;
    
                 
    
                  for(i = 0; i < size; i++)
    
                         printf("%d", data[i]);
    
                  printf("\n");
    
           }
    
           return 0;
    
    }

# **约瑟夫环** #

void f()
    
    {
    
           int n , k , m , i , j , start;
    
           while(cin>>n>>k>>m )   //n代表有多少个人 , k表示叫到k的人出列 , m 表示第一次谁先开始叫
    
           {
    
                  start = 0;
    
                  if( !n && !k && !m)
    
                         return 0;
    
                  for(i = 1 ;i < n; i++)
    
                  {
    
                         start = (start + k) % i;
    
                  }
    
                  start++;
    
                  start = (start + m) % n;
    
                  if(!start)
    
                         cout<<n<<endl;
    
                  else
    
                         cout<<start<<endl;
    
           }
    
           return ;
    
    }
    
    #include <stdio.h>
    
    main()
    
    {
    
       int n, m, i, s=0;
    
       printf ("N M = "); scanf("%d%d", &n, &m);
    
       for (i=2; i<=n; i++) s=(s+m)%i;
    
       printf ("The winner is %d\n", s+1);
    
    }