数论算法.docx
- 文档编号:6084591
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:9
- 大小:17.53KB
数论算法.docx
《数论算法.docx》由会员分享,可在线阅读,更多相关《数论算法.docx(9页珍藏版)》请在冰点文库上搜索。
数论算法
数论
素数问题、同余问题、中国剩余定理、Nim积、高斯消元法求线性方程组解、Pell方程、polya计数、矩阵二分快速幂、伪素数、基本数值计算方法(定积分求解,多项式求根,周期性方程)
1、与整数除法运算相关的算法
整除问题:
xx算法及利用其求最小公倍数:
拓展欧几里得算法及利用其解线性同余方程:
a^b%c几种计算方法
xx剩余定理
#include
usingnamespacestd;
intext_gcd(inta,intb,int&x,int&y){inttmp,d;
if(b==0){x=1;
y=0;
returna;}d=ext_gcd(b,a%b,x,y);
tmp=x;
x=y;
y=tmp-a/b*y;
returnd;}intChina_theory(inta[],intb[],intn){intres=0,m,*m1,M=1,temp;
m1=newint[n];
memset(m1,0,sizeof(m1));
for(inti=0;i M*=a[i]; for(inti=0;i ext_gcd(m,a[i],m1[i],temp); res=res%M+(m*m1[i]*b[i])%M;-- res=(res+M)%M;}deletem1; returnres;}intmain(){int*a,*b,n; while(scanf("%d",&n)&&n! =0){a=newint[n]; b=newint[n]; 2、素数相关问题 素数无穷性证明: //xx的精彩反证: /* 假设结论不成立,即只有有限多的素数p1,p2,...,pn。 令m=1+TT(1<=i<=n)pi,即所有素数的乘积,再加一。 因为这个m比所有的素数都大,因此一定是合数。 换句换说,某个素数能够整除它。 哪一个素数能整除它呢? 不难知道,m不能被p1整除,因为m除以p1的余数为1。 同样的,m也不能被p2整除,因为余数也是1。 事实上,当m除以任何一个pi时,余数总是1。 如果m真是合数,唯一的可能是: p1,p2,...,pn并没有包括所有的素数。 但这又和假设矛盾。 结论: 素数有无穷多个! */ /* 素数不仅是无穷多的,而且还不算特别少。 不超过x的素数大约有x/lnx个。 换句话说: 大约每lnx个整数中就有一个是素数。 */ 筛法求素数: #include #include #include usingnamespacestd; voidprime(bool*&b,intn){inti,j; b=newbool[n]; memset(b,1,sizeof(b)); b[0]=0; for(i=2;i<=sqrt(n)+1;i++) if(b[i-1]) for(j=1;i-1+j*i b[i-1+j*i]=0; for(i=0;i if(b[i]) printf("%d\n",i+1); }for(inti=0;i scanf("%d",&a[i]); for(inti=0;i scanf("%d",&b[i]); printf("%d\n",China_theory(a,b,n)); deletea; deleteb;}return0;} 2、比较优化的方法(不用打素数表) intdivide(__int64n){memset(a,0,sizeof(a)); __int64i,k=0; for(i=2;i<=sqrt(double(n));i++){if(n%i==0){while(n%i==0){n/=i; a[k]++;}k++;}} if(n! =1)a[k++]++; returnk;}{ intn,h; while(scanf("%d",&n)! =EOF){for(intj=0;j a[j].y=0;}h=grid(a,n); devide(a,n,h); for(inti=0;i =0) printf("%d%d\n",a[i].x,a[i].y);}} return0;}N! 末尾0的个数 用N一直除5,知道商为0,将各次商相加即得答案 N! 的素因子分解: #include #include usingnamespacestd; voidprime(bool*&b,intn){ inti,j; b=newbool[n]; memset(b,1,sizeof(b)); b[0]=0; for(i=2;i<=sqrt(n)+1;i++){ if(b[i-1]) for(j=1;i-1+j*i b[i-1+j*i]=0;}intcount_mod(inta,intn){ intsum=0,i=a; xx公式: xxφ函数: φ(n)是所有小于n的正整数里,和n互素的整数的个数。 n是一个正整数。 欧拉证明了下面这个式子: 如果n的标准素因子分解式是p1^a1*p2^a2*……*pm^am,其中众pj(j=1,2,……,m)都是素数,而且两两不等。 则有φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pm)利用容斥原理可以证明它。 *写程序的时候,公式貌似不可以用 不借助质数表 inteuler(intn){ intm=n,i; if(n%2==0)m/=2; while(n%2==0)n/=2; for(i=3;n! =1;i+=2){ if(n%i==0)m-=m/i; while(n%i==0)n/=i;}returnm;}借助质数表 constintmaxn=400; boolpf[maxn]; intp[maxn],numOfP=0; voidinit(){ memset(pf,0,sizeof(pf)); for(inti=2;i if(! pf[i]){ p[numOfP++]=i; for(intj=i*i;j pf[j]=true;}}}inteuler1(intn){ intsum=1; inttmp; for(inti=0;i if(n==1)break; if(n%p[i]==0){ tmp=0; while(n%p[i]==0){ n/=p[i]; tmp++;}for(;a<=n;a*=i) sum+=n/a; returnsum;}intmain(){ inti,n; bool*b; while(scanf("%d",&n)! =EOF){ prime(b,n); for(i=0;i if(b[i]) printf("%d%d\n",i+1,count_mod(i+1,n));}return0;}反素数: 数论四大经典定理: 威尔逊定理: 若p为质数,则p可整除(p-1)! +1。 xx定理(也称xx-xx定理) 若n,a为正整数,且n,a互素,(a,n)=1,则a^φ(n)≡1(modn) xx定理(又称xx剩余定理) 公元前后的《孙子算经》中有“物不知数”问题: “今有物不知其数,三三数之余二,五五数之余三,七七数之余二,问物几何? ”答为“23”。 明朝程大位用歌谣给出了该题的解法: “三人同行七十稀,五树梅花廿一枝,七子团圆月正半,除百零五便得知。 ”以现代的说法,是找出三个关键数70,21,15。 解法的意思就是用70乘3除所得的余数,21乘5除所得的馀数,15乘7除所得的余数,然後总加起来,除以105的余数就是答案。 费马小定理 假如p是质数,且(a,p)=1,那么a^(p-1)≡1(modp)。 假如p是质数,且a,p互质,那么a的(p-1)次方除以p的余数恒等于1。 for(intj=1;j sum*=p[i]; sum*=p[i]-1;}} if(n==1) returnsum; else returnsum*(n-1);}inteuler2(intn){inti; for(i=2;i<=sqrt((double)n);i++){ if(n%i==0&&! pf[i]){ n/=i; if(n%i==0) returni*euler2(n); else return(i-1)*euler2(n);}} returnn-1;}Poj1730 PerfectPthPowers TimeLimit: 1000MSMemoryLimit: 100K TotalSubmissions: 10870Accepted: 2429 Description Wesaythatxisaperfectsquareif,forsomeintegerb,x=b2 .Similarly,xisaperfectcubeif,forsomeintegerb,x=b3 .Moregenerally,xisaperfectpthpowerif,forsomeintegerb,x=bp .Givenanintegerxyouaretodeterminethelargestpsuchthatxisaperfectpthpower. Input Eachtestcaseisgivenbyalineofinputcontaingx.Thevalueofxwillhavemagnitudeatleast2andbewithintherangeofa(32-bit)intinC,C++,andJava.Alinecontaing0followsthelasttestcase. Output Foreachtestcase,outputalinegivingthelargestintegerpsuchthatxisaperfectpthpower. SampleInput 17 24 250SampleOutput1302程序 #include #include #include #include #definemax100 usingnamespacestd; __int64a[max]; inline intdivide(__int64n){memset(a,0,sizeof(a)); __int64i,k=0; for(i=2;i<=sqrt(double(n));i++){if(n%i==0){while(n%i==0){n/=i; a[k]++;}k++;}} if(n! =1)a[k++]++; returnk;}inline intgcd(inta,intb){if(b==0)returna; elsereturngcd(b,a%b);}intmain(){__int64n; while(scanf("%I64d",&n)&&n! =0){__int64h,m,g=0; __int64p; if(n<0)p=-n; elsep=n; m=divide(p); for(h=0;h while(g%2==0) g/=2; printf("%I64d\n",g);}return0;}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数论 算法