一. 素数筛、素数表
1.小区间素数（1e6、1e7）：
bool notprime[MAXN+10]; //判断i是否为素数 int prime[MAXN+10]; //存放素数 void getPrime() { memset(notprime, false, sizeof(notprime)); notprime[0] = notprime[1] = true; prime[0] = 0; //存放素数个数 for (int i = 2; i<=MAXN; i++) { if (!notprime[i])prime[++prime[0]] = i; for (int j = 1; j<=prime[0]&& prime[j]<=MAXN/i; j++) { notprime[prime[j]*i] = true; if (i%prime[j] == 0) break; /* 当i为合数且能被prime[j]整除时，i*prime[j+1] = k*prime[j]*prime[j+1] = k*prime[j+1]*prime[j] = i'*prime[j]，可知肯定能够在后面被prime[j]乘以 一个更大的数i'筛掉。因此，当prime[j]能整除i时，就应该退出循环，保证每 个合数只被它的最小素因子筛掉。 */ } } }
2.大区间素数筛（1e12）：
int prime[MAXN+10]; bool notprime[MAXN+10]; void getPrime() { memset(notprime, false, sizeof(notprime)); notprime[0] = notprime[1] = true; for(int i = 2; i<=MAXN; i++) { if(!notprime[i]) prime[++prime[0]]=i; for(int j = 1; j<=prime[0]&&prime[j]<=MAXN/i; j++) { notprime[prime[j]*i] = 1; if(i%prime[j]==0) break; } } } void getPrime2(int L, int R) { memset(notprime, false, sizeof(notprime)); for(int i = 1; i<=prime[0]&& prime[i]<=R/prime[i]; i++) for(int j = max(2,(int)ceil(1.0*L/prime[i])); j<=R/prime[i]; j++) notprime[j*prime[i]-L+1] = true; }
3.题目：
LightOJ1259 Goldbach`s Conjecture（素数表）
LightOJ1197 Help Hanzo（大区间素数筛）
二.唯一分解定理
1.模板：
bool notprime[MAXN]; int prime[MAXN/10]; void getPrime() { memset(notprime, false, sizeof(notprime)); notprime[0] = notprime[1] = true; prime[0] = 0; for (int i = 2; i<MAXN; i++) { if (!notprime[i])prime[++prime[0]] = i; for (int j = 1; j<=prime[0]&& prime[j]<MAXN/i; j++) { notprime[prime[j]*i] = true; if (i%prime[j] == 0) break; } } } int fatCnt; LL factor[1000][2]; int getFactors(LL n) { LL tmp = n; fatCnt = 0; for(int i = 1; prime[i]<=tmp/prime[i]; i++) { if(tmp%prime[i]==0) { factor[++fatCnt][0] = prime[i]; factor[fatCnt][1] = 0; while(tmp%prime[i]==0) tmp /= prime[i], factor[fatCnt][1]++; } } if(tmp>1) factor[++fatCnt][0] = tmp, factor[fatCnt][1] = 1; }
2.题目：
poj2773
poj3904 Sky Code
UVA1635 Irrelevant Elements
LightOJ1341 Aladdin and the Flying Carpet
LightOJ1336 Sigma Function
LightOJ1236
LightOJ1138
LightOJ1220
三. 欧几里得、扩展欧几里得
1.欧几里得算法：
LL gcd(LL a, LL b) { return b==0?a:gcd(b,a%b); }
辗转相除法证明：
设 d = gcd（a，b），
那么 d | a 、d | b …… 符号“|”表示整除
可知a可表示为：a = k*b + r，移项得：r = a - k*b，两边模d，
那么：r%d = a%d - k*b%d = 0，
所以 d | r ，所以 gcd（b，r）= gcd（a，b）。
2.扩展欧几里得：
LL exgcd(LL a, LL b, LL &x, LL &y) { if(a==0 &&b==0) return -1; if(b==0) {x=1; y=0; return a;} LL d = exgcd(b,a%b,y,x); y -= a/b*x; return d; }
2.1.算法证明：
设如下两个方程：
ax+by = gcd(a,b) ；
bx’+(a%b)y’ = gcd(b,a%b)；
又因为：gcd(a,b) = gcd(b,a %b)，
那么ax+by = bx’+(a%b)y’ = bx’ +(a – a/b*b)*y’ = ay’ + b(x’ – a/b*y’)，
由恒等关系有： x = y’ , y = (x’ – a/b*y’)
2.2.1.求 a*x + b*y = gcd（a，b） = d 的一组解，其中要求a>0、b>0。
假设求得一组解为 （x0，y0），那么通解为：（x0+k*b/ d，y0-k*a/ d），k为整数。
2.2.2.求 a*x + b*y = c 的一组解，其中要求a>0、b>0。
先求出 gcd（a，b），如果 gcd（a，b）不能整除c，则无解。如果能整除：
求出a*x + b*y = gcd（a，b）= d 的一组解（x0，y0），那么通解为 （x0*c/d+k*b/d，y0*c/d-k*a/d），k为整数。
3.题目：
POJ1061 青蛙的约会
POJ2115 C Looooops
HackerRank leonardo-and-lucky-numbers
POJ The Balance
四.欧拉函数
1. 公式：
euler（n）= n*[ (1-1/p1)*(1-1/p2)……*(1-1/pk) ]，p为n的质因子。公式根据容斥原理（展开后可知），中括号内的为百分比。
2.筛法欧拉函数：
int euler[MAXN]; void getEuler() { memset(euler, 0, sizeof(euler)); euler[1] = 1; for(int i = 2; i<MAXN; i++) if(!euler[i]) { for(int j = i; j<MAXN; j += i) { if(!euler[j]) euler[j] = j; euler[j] = euler[j]/i*(i-1); } } }
3.题目：