欧拉函数模板

欧拉函数 模板 个人简介word模板免费下载关于员工迟到处罚通告模板康奈尔office模板下载康奈尔 笔记本 模板 下载软件方案模板免费下载 篇一:ACM数学模板 2.扩展欧几里得(求ax+by = gcd(a,b)的特解) voide_gcd(LL a, LL b, LL &d, LL &x, LL &y){ if(b==0){ x = 1; y = 0; d = a; } else{ e_gcd(b, a%b, d, y, x); y-= x*(a/b); } } 3.中国剩余定理 同余方程组 x ? a1(mod m1) x ? a2(mod m2) ... ... x ? ak(mod mk) 1 方程组所有的解的集合就是: x1 = N1*a1 + N2*a2 + ... + Nk*ak 其中 Ni mod mi = 1，Ni = ai * ti , 可用欧几里得扩展定理求 ti. 其中M = m1*m2*m3????*mn; //互质版 #include <iostream usingnamespacestd; //参数可为负数的扩展欧几里德定理 voidexOJLD(int a, int b, int&x, int&y){ //根据欧几里德定理 if(b == 0){//任意数与0的最大公约数为其本身。 x = 1; y = 0; }else{ int x1, y1; exOJLD(b, a%b, x1, y1); if(a*b <0){//异号取反 x = - y1; y = a/b*y1 - x1; }else{//同号 x = y1; y = x1 - a/b* y1; 2 } } } //剩余定理 intcalSYDL(int a[], int m[], int k){ int N[k];//这个可以删除 int mm = 1;//最小公倍数 int result = 0; for(inti = 0; i< k; i++){ mm *= m[i]; } for(int j = 0; j < k; j++){ int L, J; exOJLD(mm/m[j], -m[j], L, J); N[j] = m[j] * J + 1;//1 N[j] = mm/m[j] * L;//2 【注】1和2这两个值应该是相等的。result += N[j]*a[j]; } return (result % mm + mm) % mm;//落在(0, mm)之间，这么写是为了防止result初始为负数，本例中不可能为负可以直接 写成:return result%mm;即可。 } 3 intmain(){ inta[3] = {2, 3, 2}; intm[3] = {3, 5, 7}; cout<<结果:<<calSYDL(a, m, 3)<<endl; } //不互质版 /** 中国剩余定理(不互质) */ #include <iostream #include <cstdio #include <cstring using namespace std; typedef long long LL; LL Mod; LL gcd(LL a, LL b) if(b==0)return a; return gcd(b,a%b); } LL Extend_Euclid(LL a, LL b, LL&x, LL& y) { if(b==0) {x=1,y=0;return a; } LL d = Extend_Euclid(b,a%b,x,y); LL t = x; x = y; y = t - a/b*y; return d; } //a在模n乘法下的逆元，没有则返回-1 LL inv(LL a, LL n) { LL x,y; LL t = Extend_Euclid(a,n,x,y); 4 if(t != 1)return -1; return (x%n+n)%n; } //将两个方程合 并为一个 bool merge(LL a1, LL n1, LL a2, LL n2, LL& a3, LL& n3) { LL d = gcd(n1,n2); LL c = a2-a1; if(c%d)return false; c = (c%n2+n2)%n2; c /= d; n1 /= d; n2 /= d; c *= inv(n1,n2); c %= n2; c *= n1*d; n3 = n1*n2*d; a3 = (c%n3+n3)%n3; return true; } //求模线性方程组x=ai(mod ni),ni可以不互质 LL China_Reminder2(intlen, LL* a, LL* n) { LL a1=a[0],n1=n[0]; LL a2,n2; for(inti = 1; i<len; i++) {LL aa,nn;a2 = a[i],n2=n[i];if(!merge(a1,n1,a2,n2,aa,nn)) return -1;a1 = aa;n1 = nn; } Mod = n1; return (a1%n1+n1)%n1; } LL a[1000],b[1000]; int main() { inti; int k; while(scanf(%d,&k)!=EOF) {for(i = 0; i< k; i++) scanf(%I64d %I64d,&a[i],&b[i]);printf(%I64d\n,China_Reminder2(k,b,a)); } return 0; } 4.欧拉函数(求一个数前面的所有与这个数互质的数的 个数) Euler函数表达通式: euler(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn),其中 p1,p2……pn为x的所有素{ res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出 5 while(a%i==0) a/=i; } } if(a1) res=res/a*(a-1); return res; } //线性筛选欧拉函数O(n)用到了一下性质: //(1) 若(N%a==0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a; //(2) 若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1); //注意:如果范围过大 可能不适宜开数组来做 inteuler[maxN], vis[maxN], prime[maxN/5], e[maxN], cnt = 0; void make_euler(){ memset(vis, 0, sizeof(vis)); euler[1] = 1; for(inti=2; i<maxN ; ++i){ if(vis[i] == 0){ prime[cnt++] = i; euler[i] = i-1; } for(int j=0 ; j<cnt&&i*prime[j] <maxN; 6 ++j){ vis[i*prime[j]] = 1; if( i%prime[j] == 0){ euler[i*prime[j]] = euler[i] *prime[j];break; } else euler[i*prime[j]] = euler[i] *(prime[j]-1); } } } 篇二:ACM算法竞赛模板个人 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 数 学 ................................................................................................................................................ 4 最大公约数、最小公倍 数 ....................................................................................................... 4 最大公约数——欧几里得算法 O(n) ...................................................................................... 4 Stein算法 O( log(max(a,b)) ) ........................................................................................... 4 最小公倍 数: ............................................................................................. 7 .............................. 4 素数相 关 ................................................................................................................................... 5 普通素数判 断 ................................................................................................................... 5 筛法求素数[1， N] ........................................................................................................... 5 二次筛法求素数[L， R] ................................................................................................... 6 Miller-Rabbin素数测试方 法 ........................................................................................ 7 算术基本定理的定义和性 质: ............................................................................................... 8 同余方程[组] 乘法模逆元 中国剩余定 理 ........................................................................... 9 扩展欧几里得，求一组解x，y，使得gcd(a,b) = d = a * x + b * y ................. 9 8 扩展欧几里得，求所有解x，y，使得c = a * x + b * y ..................................... 10 扩展欧几里得，求a关于n的逆元a1，使得a * a1 ? 1(mod n) ............... 10 扩展欧几里得，求解x，满足同余方程组x ? Ri(mod Ai) ................................... 10 扩展欧几里得，求解x，满足高次同余方程A ? B(mod C) ............................... 11 中国剩余定 理: ............................................................................................. ........................ 13 中国剩余定理最小非负数解的算 法: ................................................................................. 14 求解a*x + b*y = c的其中一组解，使得|x| + |y|尽可能小， 若相等，则a|x| + b|y|尽可能 小。 ............................................................................................. ................ 15 整数快速 幂 ................................................................................................. ............................ 16 矩阵快速 9 幂 ............................................................................................................................. 16 整数分 解 ................................................................................................................................. 18 试除法整数分 解 ............................................................................................................. 18 筛法整数分 解 ................................................................................................................. 18 PollardRho大整数分 解 ................................................................................................ 19 欧拉函 数 ................................................................................................................................. 22 直接欧拉函 数 ................................................................................................................. 22 递推快速求欧拉函 数 ................................................................................................. 10 .... 23 容斥原 理 ................................................................................................................................. 23 母函 数..................................................................................................................................... 24 普通母函 数 ..................................................................................................................... 24 指数型母函 数 ................................................................................................................. 25 其他相 关 ................................................................................................................................. 27 九余数定理:一个数N各位数字的和，对9取余等于这 个数对9取余 ................. 27 给你一个奇数N，求1~N的奇数平方和: S = N*(N+1)*(N+2)/6 .......................... 27 约瑟夫问题:有N个人， 编号为1~N，按顺时针围成一个圈，每数k个人，就将这 个人从圈中消除，问:最终只留下一个人的编 11 号。 ................................................. 27 给你整数x和y的和 以及x和y的积，是否能找到满足这两个式子的整数x和整 数 y。 ................................................................................................................................... 29 Fibonacci数列大于40前四位数 字 ............................................................................ 29 小于N的素数个数为π(N),π(N)的位数是多 少, ................................................... 29 Stirling公式:当N足够大时，N! = (N/e) * N * sqrt(2*pi*N)。 .................. 29 有N张卡，将N张卡分成若干不同的集合，集合不能为空。 问:总共有多少种分法。 ......................................................................................................................................... 29 字符 串 ............................................................................................................................................ 29 KMP........................................................................................................................................... 29 12 1. 既能做前缀又能做后缀的子串长 度 ....................................................................... 30 2.求最短子串长 度 ......................................................................................................... 30 3.求模式串pat在主串str中匹配次 数 ..................................................................... 30 4.求N行M列的字符矩阵，最小的字符子矩阵的面 积 ............................................. 30 5.求字符串s的循环前缀的长度和循环的次 数 ......................................................... 30 字典 树..................................................................................................................................... 31 数据结 构......................................................................................................................................... 33 并查 集..................................................................................................................................... 33 树状数 组 ................................................................................................. 13 ................................ 33 单点更新，区间求值:树状数组代表区间的 和。 ..................................................... 33 区间更新，单点求值:树状数组代表单个元素的变 化 ............................................. 34 求逆序数: 数组Tree[i] 表示数字i是否在序列中出现过，如果数字i已经存在于序 列中，Tree[i] = 1，否则Tree[i] = 0。按序列从左到右将值为 a的元素当作下标为a，赋值为1插入树状数组里，这时， 比a的数个数就是i - Query(a)。 将全部结果累加起来就是逆序数 了。 ......................................................................... 35 二维树状数 组: ............................................................................................................. 36 线段 树..................................................................................................................................... 36 单点更 新 ......................................................................................................................... 37 成段更 新 ................................................................................................. 14 ........................ 43 区间合 并 ......................................................................................................................... 52 扫描 线 ............................................................................................................................. 54 图 论 .............................................................................................................................................. 58 图的五种种存储方 式 ............................................................................................................. 58 方式1:邻接矩 阵 .......................................................................................................... 58 方式2:前向 星 .............................................................................................................. 58 方式3:邻接表——动态建 表 ...................................................................................... 59 方式4:邻接表——vector模拟链表实 15 现 ................................................................. 60 方式5:邻接表——链式前向星 ? .............................................................................. 61 拓扑排 序 ................................................................................................................................. 62 最小生成 树 ............................................................................................................................. 63 Kruskal算 法: .............................................................................................................. 63 Prim算 法: .................................................................................................................... 64 次小生成 树 ............................................................................................................................. 66 最小树形 图 ............................................................................................................................. 68 最近公共祖先LCA—Tarjan-LCA算 16 法: ............................................................................. 72 树的最小支配集、最小点覆盖、最大独立 集 ..................................................................... 74 最小支配集:指从所有顶点中取尽量少的点组成一个集 合，使得剩下的所有点都与取出来的点有边相连。顶点个数 最小的支配集被称为最小支配集。这里用贪心法来 求。 ................................................................................................................................. 74 最小点覆盖:指从所有顶点中取尽 量少的点组成一个集合，使得集合中所有的边都 与取出来的点有边相连。顶点个数最小的覆盖集被称为最 小点覆盖。 ................. 76 最大独立集:指从所有顶点中取 尽量多的点组成一个集合，使得这些点之间没有边 相连。顶点个数最多的独立集被称为最大独立 集。 ................................................. 77 单源最短路径Dijkstra、BellmanFord、 SPFA .................................................................. 77 Dijkstra算 法: ............................................................................................................ 77 BellmanFord算 法: ............................................................................................. 17 ......... 79 SPFA算 法: .................................................................................................................... 81 多源最短路径Floyd、Floyd求最小 环 ............................................................................... 84 Floyd算法:用来找出每对点之间的最短距离。图可以是 无向图，也可以是有向图， 边权可为正，也可以为负，唯一要求是不能有负 环。 ............................................. 84 Floyd求最小 环 .............................................................................................................. 85 K短路—A*+SPFA算 法: ....................................................................................................... 86 差分约束系 统 ......................................................................................................................... 89 强连通分量Kosaraju、 Tarjan ............................................................................................ 92 18 Kosaraju算 法: ............................................................................................................ 92 Tarjan算 法: ................................................................................................................ 94 2-SAT....................................................................................................................................... 97 二分 图................................................................................................................................... 100 二分图最大匹配——匈牙利算法DFS 版: ............................................................... 100 二分图多重 匹 配: ....................................................................................................... 101 二分图最佳匹配——KM算 法: .................................................................................. 102 网 络流最大流EdmondKarp、 SAP ........................................................................................ 104 EdmondKarp算 法: ...................................................................................................... 104 SAP算 19 法: ............................................................................................. ....................... 106 输入输出外挂—仅适合纯数字输入 ................................................................................... 109 数 学 最大公约数、最小公倍数 最大公约数、最小公倍数性质: 1.若a | m，b | m，则lcm(a，b) | m。 2.若d | a，d | b，则d | gcd(a，b)。 3.lcm(a，b) = a * b / gcd(a，b)。 4.设m，a，b是正整数，则lcm(m*a，m*b) = m * gcd(a，b) 5.若m是非零整数a1，a2，…，an的公倍数，则lcm(a1，a2，…，an) | m用素因子分解法求a和b的最大公约数和最小公倍数: a = p1 1 * p2 2 * … * pk k b = p1 1 * p2*s2 * … * pk k gcd(a，b) = p1 20 in(r1,s1) * p2 21 in(r2,s2) * … * pk 22 in(rk,sk) lcm(a，b) = p1 23 ax(r1,s1) * p2 24 ax(r2,s2) * … * pk 25 ax(rk,sk) 最大公约数——欧几里得算法O(n) int GCD(int a,int b) { if(a < b) int temp = a, a = b, b = temp; if(b == 0) return a; return GCD(b,a%b); } Stein算法O( log(max(a,b)) ) int KGCD(int a,int b) { if(a == 0) return b; if(b == 0) return a; if(~a & 1) { if(b & 1) return KGCD(a1, b); else return KGCD(a1, b1) << 1; } if(~b & 1) return KGCD(a, b1); if(a b) return KGCD((a-b)1, b); return KGCD((b-a)1, a); } 26 最小公倍数: int LCM(int a,int b) { return a/KGCD(a,b)*b; 。 } 素数相关 素数和合数共同的性质: 1.a 1是合数，当且仅当a = b * c，其中1 < b < a，1 < c < a。 2.合数必有素数因子。 3.如果d 1，p是素数，且d | q，则d = p。 4.设p是素数且p | a*b，则必有p | a或者p | b。 素数的性质: 1.存在无穷多个素数。 2.每个大于1的正整数都有一个素因子。 素数的分布: 素数定理:用π(x)估计小于正整数x的素数有多少个。随着x的增长，π(x) / (x/ln x) = 1。 推论:令pn是第n个素数，其中n是正整数，那么pn ~ n*ln n。 素数的猜想: 1.波特兰猜想:对于任意给定的正整数n，其中n 1，存 27 在一个素数p，使得n < p < 2*n。 2.孪生素数猜想:存在无穷多的形如p和p+2的素数对。 3.哥德巴赫猜想:每个大于2的正偶数可以写成两个素数的和。可推出任一大于7的奇数都可写成三个质数之和的猜想。 普通素数判断 int IsPrime(int N)//注意#include<cmath { if(N <= 1) return 0; int i; for(i = 2; i <= sqrt(N*1.0); ++i) if(N%i == 0) return 0; return 1; } 筛法求素数[1，N] const int MAXN = 1000000; bool Prime[MAXN+100];//Prime[i] == true表示i为素数 void IsPrime() { for(int i = 2; i <= MAXN; ++i) Prime[i] = true; for(int i = 2; i <= MAXN; ++i) 28 if(Prime[i]) for(int j = i+i; j <= MAXN; j+=i) Prime[j] = false; } 篇三:数论算法模板 头文 件....................................................................................................................................... 2 求素数[1,n],返回素数个 数 ...................................................................................................... 3 得到区间 [a ,b ] 之间的素 数 ................................................................................................. 3 求 a*b%c ................................................................................................................................................................ 5 求x的欧拉函数 值 ................................................................................................................... 5 快速求欧拉函数和素 数。 ............................................................................................. 29 .......... 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 进制转 30 换 ................................................................................................................................. 14 牛顿迭代法求开 方 ................................................................................................................. 14 字符串s表示的数字对一个整数取 摸 ................................................................................. 14 得到素数m的原根,需要素数 表 ........................................................................................... 15 满足gcd(n,i) = 1 并且 i <=,成立的,的个 数 ...................................................................... 17 得到一个数字的二进制表达式的第i 位 .............................................................................. 18 求第k个与n互素的数,需要素数 表 .................................................................................... 18 求解x = a mod (n) 。n为素 数. ........................................................................................ 20 求解pell方 程 ......................................................................................................................... 20 求pell方程的第i个 解 ................................................................................................. 31 ......... 21 求解 x - a*b*y = 1。的最小解 (pell) ........................................................................ 22 求离散对数A = B mod C 模板 c不一定要素 数 ........................................................ 23 求最小x使得a = 1 mod n ............................................................................................... 26 保证pn<=L,pd<=L 并且pn/pd 最接近 A. .......................................................................... 26 m<10, 一个这样的数:M = mmm...mm,要求 M%k=0. ......................................................... 28 求n所有的约数 和 ......................................................................................................................... 32 求最大的并且不大于n的最大反素 数 ................................................................................. 33 整数HASH ,用以统一每个数字出现的次 数 ....................................................................... 34 同上，速度较快的一 种 ......................................................................................................... 37 32 Sum(gcd(x,y) ) 1<=x,y<=n ................................................................................................... 38 大整数因数分 解 ..................................................................................................................... 39 三分模 板 ................................................................................................................................. 42 哥德巴赫猜 想 ......................................................................................................................... 42 梅森合数的因数分 解 ............................................................................................................. 43 计算前n个Catalen数和 mod m ....................................................................................... 44 矩阵相 关 ............................................................................................................................... 46 头文件 #include <stdio.h 33 #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; template<class Tinline T iabs(const T& v) {return v<0 ? -v : v;} 34 template<class Tinline T strTo(string s){istringstream is(s);T v;isv;return v;} template<class Tinline string toStr(const T& v){ostringstream os;os<<v;return os.str();} template<class Tinline int cMin(T& a, const T& b){return b<a?a=b,1:0;} template<class Tinline int cMax(T& a, const T& b){return a<b?a=b,1:0;} template<class 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],返回素数个数 bool is[1000010];//用来求素数[1,130000] int prm[100000];//用来保存素数 int totleprm;//记录素数总个数 void getprm(int n) 35 { int i; 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 (int s=2*i,j=i*i; j<=n; j+=s) is[j]=0; } for (; i<=n; i++) if (is[i]) prm[totleprm++]=i; } 得到区间 [a ,b ] 之间的素数 注意:需要前 6000个素数 (一般) int subprm[100010]; int getSubPrm(u64 a,u64 b) { u64 totl = 0,i,j; 36 bool sign[1000010]; memset(sign,true,sizeof(sign)); if (a < 2) a = 2; u64 l = b - a + 1; for ( i=0; i<totleprm;i++) { if ((j=prm[i]*(a/prm[i]))<a) j += prm[i]; if (j<prm[i]*prm[i]) j = prm[i] * prm[i]; for ( ; j<=b ; j+=prm[i]) sign[j-a] = false; } for (i=0;i<l;i++) if (sign[i]) subprm[totl++] = a + i; return totl; } 求a*b%c 要求:a,b的范围在hugeint范围的一般以内，在hugeint 为unsigned __int64时，a,b需要是__int64能表示的数 u64 power_mod(u64 A, u64 B, u64 C) R = 1, D = A; while (B ) { if (B&1) R = product_mod(R, D, C); D = product_mod(D, D, C); 37 B =1; } return R; } 求x的欧拉函数值 注意:需要素数表 u64 euler(u64 x) { int i ; u64 res = x; for (i = 0; prm[i] < (u64 )sqrt(x * 1.0) + 1 && i < totleprm; i++) if (x % prm[i] == 0) { res = res / prm[i] *( prm[i] - 1); while (x % prm[i] == 0 ) x/=prm[i]; } if (x 1) res = res / x * (x-1); return res; } 求x的欧拉函数值 u64 phi[1000001]; void euler(int maxn) 38 { int i; int j; for (i = 2; i <= maxn; i++) phi[i] = i; for (i = 2; i <= maxn; i+=2) phi[i] /=2; for (i = 3; i <= maxn; i+=2) if (phi[i] == i) { for (j = i; j<=maxn; j+=i) phi[j] = phi[j] / i * (i-1); 相关热词搜索:函数 模板 欧拉 欧拉函数证明 欧拉函数 公式 39