ACM数论常用的模版.doc

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

1、欧几里德#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<usingnamespac

2、estd;__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("Noanswer");

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

4、usingnamespacestd;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];d=ext_euclid(W[i],m,x,y);a=(a+y*m*B[i])%n;}if(a>0)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<usingnamespacestd;intphi[1000

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

7、/=i,ret*=i;}if(n>1)ret*=n-1;returnret;//n的欧拉数}行列式计算#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=z)b[j][k]=s[j+1][k+1];else