acm+数论常用的模版

《acm+数论常用的模版》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、28欧几里德#includeusingnamespacestd;inthcf(inta,intb){intr=0;while(b!=0){r=a%b;a=b;b=r;}return(a);}lcd(intu,intv,inth)//u=a，v=b，h为最小公约数=hcf(a,b);{return(u*v/h);}intmain(){inta,b,x,y;cin>>a>>b;x=hcf(a,b);y=lcd(a,b,x);cout<usin

2、gnamespacestd;__int64ext_euclid(__int64a,__int64b,__int64&x,__int64&y){intt;__int64d;if(b==0){x=1;y=0;returna;}d=ext_euclid(b,a%b,x,y);t=x;x=y;y=t-a/b*y;returnd;}voidmodular_equation(__int64a,__int64b,__int64c)//ax=b(modn){__int64d;__int64x,y;d=ext_euclid(a,b,x,y);if(c%d!=0)printf(

3、"Noanswer");else{x=(x*c/d)%b;//第一次求出的x;__int64t=b/d;x=(x%t+t)%t;printf("%I64d",x);//最小的正数的值for(inti=0;i

4、无解.*/28中国剩余定理#includeusingnamespacestd;intext_euclid(inta,intb,int&x,int&y)//求gcd(a,b)=ax+by{intt,d;if(b==0){x=1;y=0;returna;}d=ext_euclid(b,a%b,x,y);t=x;x=y;y=t-a/b*y;returnd;}intChina(intW[],intB[],intk)//W为按多少排列，B为剩余个数W>BK为组数{inti;intd,x,y,a=0,m,n=1;for(i=0;i

5、W[i];for(i=0;i0)returna;elsereturn(a+n);}intmain(){intB[100],W[100];求intk;a=2(mod5)cin>>k;a=3(mod13)for(inti=0;i>W[i];52cin>>B[i];133}输出42cout<

6、eam>usingnamespacestd;intphi[1000];//数组中储存每个数的欧拉数voidgenPhi(intn)//求出比n小的每一个数的欧拉数(n-1的){inti,j,pNum=0;memset(phi,0,sizeof(phi));phi[1]=1;for(i=2;i

7、f(n%i==0){n/=i,ret*=i-1;while(n%i==0)n/=i,ret*=i;}if(n>1)ret*=n-1;returnret;//n的欧拉数}28行列式计算#includeusingnamespacestd;intjs(ints[100][100],intn){intz,j,k,r,total=0;intb[100][100];/*b[N][N]用于存放，在矩阵s[N][N]中元素s[0]的余子式*/if(n>2){for(z=0;z

8、k++)if(k>=z)b[j][k]=s[j+1]