数论算法模板

《数论算法模板》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、头文件2求素数[1,n],返回素数个数3得到区间[a,b]之间的素数3求a*b%c4求a^b%c4求x的欧拉函数值5求x的欧拉函数值5快速求欧拉函数和素数。6求解a*x=bmodn7求解gcd(a,b)=a*x+b*y(切忌unsigned)7x=a[i]modm[i].8求约数和模板，fac[]存储所求数的因数分解式10给出随机数，可以简单的用rand()代替10rabinmiller方法测试n是否为质数11pollard_rho分解，给出N的一个非1因数，12找出N的最小质因数13用中国剩余定理解同余方程

2、组a=bi（modni)13进制转换14牛顿迭代法求开方14字符串s表示的数字对一个整数取摸14得到素数m的原根,需要素数表15满足gcd(n,i)=1并且i<=ｍ成立的ｉ的个数16求A^B17一个数字的二进制表达式中1的个数17得到一个数字的二进制表达式的第i位18求第k个与n互素的数,需要素数表18求解x^2=amod(n)。n为素数.20求解pell方程20求pell方程的第i个解21求解x^2-a*b*y^2=1。的最小解（pell）22求离散对数A^x=BmodC模板c不一定要素数23求最小x使得a

3、^x=1modn26保证pn<=L,pd<=L并且pn/pd最接近A.26m<10,一个这样的数:M=mmm...mm,要求M%k=0.28求n所有的约数和28状态背包+梅森素数29求b^b^b…^bmodm(n个)32求最大的并且不大于n的最大反素数33整数HASH,用以统一每个数字出现的次数34同上，速度较快的一种37Sum(gcd(x,y))1<=x,y<=n38大整数因数分解39三分模板42哥德巴赫猜想4246梅森合数的因数分解43计算前n个Catalen数和modm44矩阵相关4646头文件#inc

4、lude#include#include#include#include#include#include#include

5、iostream>#include#include#includeusingnamespacestd;templateinlineTiabs(constT&v){returnv<0?-v:v;}templateinlineTstrTo(strings){istringstreamis(s);Tv;is>>v;returnv;}templateinlinestringtoStr(constT&v){o

6、stringstreamos;os<inlineintcMin(T&a,constT&b){returnbinlineintcMax(T&a,constT&b){returnainlineintcBit(Tn){returnn?cBit(n&(n-1))+1:0;}#defineep1E-10#defineCLR(arr,v)me

7、mset(arr,v,sizeof(arr))#defineSQ(a)((a)*(a))#defineDEBUG(a)printf("%s=%s",#a,toStr(a).c_str())#defineFOR(i,s,e)for(u64(i)=(s);(i)<(e);i++)Constu64inf3=0x15fffffffffffffffll;46intinf4=0x7fffffffl;typedeflonglongu64;求素数[1,n],返回素数个数boolis[1000010];//用来求素数[1,

8、130000]intprm[100000];//用来保存素数inttotleprm;//记录素数总个数voidgetprm(intn){inti;memset(is,1,sizeof(is));is[1]=0;prm[totleprm++]=2;for(i=4;i<=n;i+=2)is[i]=0;for(i=3;i*i<=n;i+=2)if(is[i]){prm[totleprm++]=i;for(