數(shù)論算法模板

《數(shù)論算法模板》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、頭文件2求素數(shù)[1,n],返回素數(shù)個數(shù)3得到區(qū)間[a,b]之間的素數(shù)3求a*b%c4求a^b%c4求x的歐拉函數(shù)值5求x的歐拉函數(shù)值5快速求歐拉函數(shù)和素數(shù)。6求解a*x=bmodn7求解gcd(a,b)=a*x+b*y(切忌unsigned)7x=a[i]modm[i].8求約數(shù)和模板，fac[]存儲所求數(shù)的因數(shù)分解式10給出隨機數(shù)，可以簡單的用rand()代替10rabinmiller方法測試n是否為質(zhì)數(shù)11pollard_rho分解，給出N的一個非1因數(shù)，12找出N的最小質(zhì)因數(shù)13用中國剩余定理解同余方程

2、組a=bi（modni)13進制轉(zhuǎn)換14牛頓迭代法求開方14字符串s表示的數(shù)字對一個整數(shù)取摸14得到素數(shù)m的原根,需要素數(shù)表15滿足gcd(n,i)=1并且i<=ｍ成立的ｉ的個數(shù)16求A^B17一個數(shù)字的二進制表達式中1的個數(shù)17得到一個數(shù)字的二進制表達式的第i位18求第k個與n互素的數(shù),需要素數(shù)表18求解x^2=amod(n)。n為素數(shù).20求解pell方程20求pell方程的第i個解21求解x^2-a*b*y^2=1。的最小解（pell）22求離散對數(shù)A^x=BmodC模板c不一定要素數(shù)23求最小x使得a

3、^x=1modn26保證pn<=L,pd<=L并且pn/pd最接近A.26m<10,一個這樣的數(shù):M=mmm...mm,要求M%k=0.28求n所有的約數(shù)和28狀態(tài)背包+梅森素數(shù)29求b^b^b…^bmodm(n個)32求最大的并且不大于n的最大反素數(shù)33整數(shù)HASH,用以統(tǒng)一每個數(shù)字出現(xiàn)的次數(shù)34同上，速度較快的一種37Sum(gcd(x,y))1<=x,y<=n38大整數(shù)因數(shù)分解39三分模板42哥德巴赫猜想4246梅森合數(shù)的因數(shù)分解43計算前n個Catalen數(shù)和modm44矩陣相關(guān)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;求素數(shù)[1,n],返回素數(shù)個數(shù)boolis[1000010];//用來求素數(shù)[1,

8、130000]intprm[100000];//用來保存素數(shù)inttotleprm;//記錄素數(shù)總個數(shù)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(