数论基础代码合集
【摘要】 欧几里德
#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...
欧几里德
-
#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);
-
-
}
文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。
原文链接：fantianzuo.blog.csdn.net/article/details/104085092
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）