数论算法模板.docVIP

头文件 2 求素数[1,n],返回素数个数 3 得到区间 [a ,b ] 之间的素数 3 求a*b%c 4 求a^b%c 4 求x的欧拉函数值 5 求x的欧拉函数值 5 快速求欧拉函数和素数。 6 求解 a * x = b mod n 7 求解 gcd (a,b) = a * x + b * y (切忌unsigned) 7 x = a[i] mod m[i] . 8 求约数和模板，fac[]存储所求数的因数分解式 10 给出随机数，可以简单的用rand()代替 10 rabinmiller方法测试n是否为质数 11 pollard_rho分解，给出N的一个非1因数， 12 找出N的最小质因数 13 用中国剩余定理解同余方程组a=bi（modni) 13 进制转换 14 牛顿迭代法求开方 14 字符串s表示的数字对一个整数取摸 14 得到素数m的原根,需要素数表 15 满足gcd(n,i) = 1 并且 i =ｍ成立的ｉ的个数 16 求A^B 17 一个数字的二进制表达式中1的个数 17 得到一个数字的二进制表达式的第i位 18 求第k个与n互素的数,需要素数表 18 求解x^2 = a mod (n) 。n为素数. 20 求解pell方程 20 求pell方程的第i个解 21 求解 x^2 - a*b*y^2 = 1。的最小解（pell） 22 求离散对数A^x = B mod C 模板 c不一定要素数 23 求最小x使得a^x = 1 mod n 26 保证pn=L,pd=L 并且pn/pd 最接近A. 26 m10, 一个这样的数:M = mmm...mm,要求M%k=0. 28 求n所有的约数和 28 状态背包+梅森素数 29 求b^b^b…^b mod m (n个) 32 求最大的并且不大于n的最大反素数 33 整数HASH ,用以统一每个数字出现的次数 34 同上，速度较快的一种 37 Sum(gcd(x,y) ) 1=x,y=n 38 大整数因数分解 39 三分模板 42 哥德巴赫猜想 42 梅森合数的因数分解 43 计算前n个Catalen数和 mod m 44 矩阵相关 46 头文件 #include stdio.h #include string.h #include stdlib.h #include ctype.h #include math.h #include time.h #include set #include map #include stack #include queue #include string #include bitset #include vector #include deque #include list #include sstream #include iostream #include functional #include numeric #include algorithm using namespace std; templateclass Tinline T iabs(const T v) {return v0 ? -v : v;} templateclass Tinline T strTo(string s){istringstream is(s);T v;isv;return v;} templateclass Tinline string toStr(const T v){ostringstream os;osv;return os.str();} templateclass Tinline int cMin(T a, const T b){return ba?a=b,1:0;} templateclass Tinline int cMax(T a, const T b){return ab?a=b,1:0;} templateclass Tinline 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 = %s\n, #a, toStr(a).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