信息学竞赛中数论常见问题

《信息学竞赛中数论常见问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Prime概述:>1的数,除了1和本身没有其他因子.1既不是素数也不是合数,0和所有的负整数同样如此.100以内的素数{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97}1.打表(1)#definen1000003intprime[n];//要判断的范围是多大,就要设置多大的数组,对应于某个数,看它下标对应的数是1，则是素数,否则,不是素数voidgetPrime(){inti,j;intbound=sqrt((double)n);for(i=2;i

2、[i]=1;//将所有的数置1，表示这些数都是素数.for(i=2;i

3、数的个数,prim[i]一次存放这pn个素数.这种方法的好处是存储素数时节省空间,输出素数时节省时间2.直接判断boolisPrime2(intx){if(x<=1)returnfalse;if(x==2)returntrue;if(x%2==0)returnfalse;doublebound=sqrt((double)x);for(inti=3;i<=bound;i+=2){if(x%i==0){returnfalse;}}returntrue;}GCD(最大公约数)---欧几里得算法a,b为正整数，设集合A={x*a+y*b

4、x,y是整数}，则A中最小正元素是

5、gcd(a,b)longkgcd(longa,longb){if(a==0)returnb;if(b==0)returna;if(!(a&1)&&!(b&1))returnkgcd(a>>1,b>>1)<<1;elseif(!(b&1))returnkgcd(a,b>>1);elseif(!(a&1))returnkgcd(a>>1,b);elsereturnkgcd(abs(a-b),min(a,b));}LCM(最小公倍数)LCM(a,b)=a*b/GCD(a,b)实际上最好写成a/GCD(a,b)*blonglcm(longa,longb){longc,d,

6、sw;c=(a>=b)?a:b;d=(a<=b)?a:b;while(c%d!=0){sw=c%d;c=d;d=sw;}return(a/d)*b;}求多个数的lcm,需要将res初始化为1相关题目:1.http://acm.hdu.edu.cn/showproblem.php?pid=1019LeastCommonMultiple2.http://acm.hdu.edu.cn/showproblem.php?pid=1222wolfandrabbit扩展欧几里得(可以求解模线性方程)a*x+b*y=gcd(a,b)一系列解是x=x+b,y=y-aintextgc

7、d(inta,intb,int&x,int&y){if(b==0){x=1;y=0;returna;}intd=extgcd(b,a%b,x,y);intt=x;x=y;y=t-a/b*y;returnd;}a*x+n*y=b==ax=b(modn)模线性方程定理：方程ax=b(modn)对于未知量x有解，当且仅当gcd(a,n)

8、b.令d=gcd(a,n).设为x',y'为所求满足ax'+ny'=gcd(a,n).则原方程有一解x0=x'*(b/d)modn.定理:假设ax=b(modn)有解,x0是该方程的任意一个解，则该方程模n恰有d个不同的解，分别为：xi

9、=(x0+i*(n/d))modn(其中i=1,2,...d-1).//a*x=b(%n)voidmodeq(__int64a,__int64b,__int64n){__int64e,d,x,y,t;d=extgcd(a,n,x,y);if(b%d)printf("Impossible");else{e=(x*(b/d))%n+n;t=n/d;t=t>0?t:-t;e%=t;if(e<0)e+=t;printf("%I64d",e);}}题目:1.http://acm.hdu.edu.cn/showproblem.php?pid=2669若n=p1e1p2

10、e2…pr