《数论算法模板》由会员分享，可在线阅读，更多相关《数论算法模板（46页珍藏版）》请在金锄头文库上搜索。
1、头文件2求素数1,n,返回素数个数3得到区间 a ,b 之间的素数3求a*b%c4求ab%c4求x的欧拉函数值5求x的欧拉函数值5快速求欧拉函数和素数。6求解 a * x = b mod n7求解 gcd (a,b) = a * x + b * y (切忌unsigned)7x = ai mod mi .8求约数和模板，fac存储所求数的因数分解式10给出随机数，可以简单的用rand()代替10rabinmiller方法测试n是否为质数11pollard_rho分解，给出N的一个非1因数，12找出N的最小质因数13用中国剩余定理解同余方程组a=bi（modni)13进制转换14牛顿迭代法求开方
2、14字符串s表示的数字对一个整数取摸14得到素数m的原根,需要素数表15满足gcd(n,i) = 1 并且 i =成立的的个数16求AB17一个数字的二进制表达式中1的个数17得到一个数字的二进制表达式的第i位18求第k个与n互素的数,需要素数表18求解x2 = a mod (n) 。n为素数.20求解pell方程20求pell方程的第i个解21求解 x2 - a*b*y2 = 1。的最小解（pell）22求离散对数Ax = B mod C 模板 c不一定要素数23求最小x使得ax = 1 mod n 26保证pn=L,pd=L 并且pn/pd 最接近A.26m10, 一个这样的数:M = m
3、mm.mm,要求M%k=0.28求n所有的约数和28状态背包+梅森素数29求bbbb mod m (n个) 32求最大的并且不大于n的最大反素数33整数HASH ,用以统一每个数字出现的次数34同上，速度较快的一种37Sum(gcd(x,y) ) 1=x,y=n 38大整数因数分解39三分模板42哥德巴赫猜想42梅森合数的因数分解43计算前n个Catalen数和 mod m 44矩阵相关 46头文件#include #include #include #include #include #include #include #include #include #include #include
4、#include #include #include #include #include #include #include #include #include using namespace std;templateinline T iabs(const T& v) return v0 ? -v : v;templateinline T strTo(string s)istringstream is(s);T v;isv;return v;templateinline string toStr(const T& v)ostringstream os;osv;return os.str();t
5、emplateinline int cMin(T& a, const T& b)return ba?a=b,1:0;templateinline int cMax(T& a, const T& b)return ab?a=b,1:0;templateinline int cBit(T n)return n?cBit(n&(n-1)+1:0;#define ep 1E-10#define CLR(arr,v) memset(arr, v, sizeof(arr)#define SQ(a) (a)*(a)#define DEBUG(a) printf(%s = %sn, #a, toStr(a).
6、c_str()#define FOR(i,s,e) for( u64 (i)=(s); (i) (e) ; i+)Const u64 inf3 = 0x15fffffffffffffffll;int inf4 = 0x7fffffffl;typedef long long u64; 求素数1,n,返回素数个数bool is1000010;/用来求素数1,130000int prm100000;/用来保存素数int totleprm;/记录素数总个数void getprm(int n) int i; memset(is,1,sizeof(is); is1=0; prmtotleprm+=2; f
7、or (i=4; i=n; i+=2) isi=0; for (i=3; i*i=n; i+=2) if (isi) prmtotleprm+=i; for (int s=2*i,j=i*i; j=n; j+=s) isj=0; for (; i=n; i+) if (isi) prmtotleprm+=i;得到区间 a ,b 之间的素数注意：需要前 6000个素数 （一般）int subprm100010;int getSubPrm(u64 a,u64 b) u64 totl = 0,i,j; bool sign1000010; memset(sign,true,sizeof(sign);
8、if (a 2) a = 2; u64 l = b - a + 1; for ( i=0; itotleprm;i+) if (j=prmi*(a/prmi)a) j += prmi; if (jprmi*prmi) j = prmi * prmi; for ( ; j=b ; j+=prmi) signj-a = false; for (i=0;i=1; return R;求ab%c要求:a,b的范围在_int64范围的一般以内，在_int64为unsigned _int64时，a,b需要是_int64能表示的数u64 power_mod(u64 A, u64 B, u64 C) u64 R
9、 = 1, D = A; while (B ) if (B&1) R = product_mod(R, D, C); D = product_mod(D, D, C); B =1; return R; 求x的欧拉函数值注意：需要素数表u64 euler(u64 x) int i ; u64 res = x; for (i = 0; prmi (u64 )sqrt(x * 1.0) + 1 & i 1) res = res / x * (x-1); return res;求x的欧拉函数值u64 phi1000001;void euler(int maxn) int i; int j; for (
10、i = 2; i = maxn; i+) phii = i; for (i = 2; i = maxn; i+=2) phii /=2; for (i = 3; i = maxn; i+=2) if (phii = i) for (j = i; j=maxn; j+=i) phij = phij / i * (i-1); 快速求欧拉函数和素数。注意：返回1,maxn中所有素数和每个数字的欧拉函数。注意：prime0 存储区间内素数个数，prime1 = 2;u64 phi150010;char ok150010=0;u64 prm150010=0;u64 sum150010=0;int totleprm;int eulerAndPrm(int maxn) u64 i,j;int totleprm=0;phi1=1; for(i=2;i=maxn;i+) if(oki=0) prmtotleprm+=i;1 phii=i-1; for(j=0;jtotleprm & prmj*i= maxn;j+) okprmj*i=1; if(i%prmj=0) phii*prmj=phii*prmj; break; else phii*prmj=phii*(prmj-1);
