写在前面
数学如同一朵鲜花
华丽的外表下
带着我的梦想
向远方出发
可是道路并不好走
充满荆棘，路面泥泞
但是我不怕
因为我手中
有着世界上最奇妙的花
于是这就是我的NOIP数学整理了，自认为比较全面了
一 基本运算
略 需要注意的一点是负数取mod:a%c=(a%c+c)%c
二 一般算法
1 快速幂与ex快速幂
快速幂：略 可以递归写 复杂度logn
ex快速幂：
求(1+a+a2+…+ab) mod p （等比数列求和）
1<=a, b, p <= 10^9
先做1+a
再做(1+a)*a^2+(1+a) 这样就是1+a+a^2+a^3 再做(1+a+a^2+a^3)*a^4+.. 递归下去 记录当前乘了a的多少次方
这样做到接近于 b的地方：
1+a+a^2+……+a^(2^k) 此时再往回乘上之前记下来的系数 同时加上自己本身 你会惊奇的发现你算出了Σa^(i-1) 再乘个a加上自己即可
2 质数判断及筛法
质数判断：
1 暴力（sqrt(n)）
2 多次判断：先筛出1-sqrt(n) 再判断
3 mr 大法好 时间复杂度log(n)
筛法：
1 未筛到的即为素数 打上标记并进入素数表
2 for 1->totp 枚举素数 保证每个数只被自己的最小素因子筛掉；
详细讲解：每个合数可以表示成p1*p2*p3*p4….的形式（指数我省略了） P数组中的素数是单调递增的，当找到第一个素因子时，就break了 绝壁是最小素因子！
这样可以保证严格单调O（N）的
3 质因数相关
神级定理：一个数最多只有一个大于sqrt(P)的质因子，且一个数的质因数非常少！-》NOI2015考啦！
分解质因数：
1 暴力分解 sqrt(n)
2 筛完了分解 要多快有多快
3 通吃-》pr算法
n!分解质因数：
筛出n以内所有素数，对于n! 可以分解为 p1^a1*p2^a2….这样的。
所以对于每个素数，每次某个素数的质数+=n/p[i]，这样把1*2*3*4*…中所以p的倍数都算了，所以就可以出每个质数的指数了。
无须担心精度问题，下取整大法好。
4 约数相关
小提示：某个数的约数的数量也很少，基于约数的暴力【乱搞】也是合适的。
计算约数：
sqrt(n) ->在sqrt(n)以内有一个约数，必定在sqrt(n)以上有对应的一个约数，+=2即可
约数个数：
每个数可以写成标准分解形式：p1^a1*p2^a2….
由约数定义可知p1^a1的约数有:p1^0, p1^1, p1^2… ，共（a1+1）个，同理p2^a2的约数有（a2+1）个……
根据乘法原理：n的约数的个数就是(a1+1)(a2+1)(a3+1)….
约数个数和
求1-n的数的约数个数：
在1-n所有数中，枚举i。i可以成为i*1,i*2,i*3…的约数。发现对于每一个i,i*1,i*2,i*3…这些数最多出现floor(n/i)次，于是for一遍即可！
5 欧拉函数：
公式：phi(n)=n*(1-1/p1)*(1-1/p2)…
不理性的思考一下，n个数中，p1是不与n互质的。。占1/p1的比例，1-这些就是互质的！最后用n乘上（我在瞎说什么）
认真的证明：（我本来想【抄】证明，发现网上的都是基于欧拉函数是积性函数的性质的，比如http://www.cnblogs.com/yefeng1627/archive/2013/01/02/2842492.html 回头再看【娱乐】吧）
不过根据这个公式并不好算欧拉函数，我们可以根据这个公式推出：
phi(x)->
phi(x*p)=phi(x)*p [x p不互质]
phi(x*p)=phi(x)*p-1[x p互质] -> 我都不会证明
也有： ↑
若(n%p==0 && (n/p)%p==0) 则有:phi(n)=phi(n/p)*p;
若(n%p==0 && (n/p)%p!=0) 则有:phi(n)=phi(n/p)*(p-1);
于是轻松算欧拉函数，还能筛欧拉函数。。
6 欧拉定理相关：
费马小定理，欧拉定理-》略
以上定理的条件是a,b互质(否则没有逆元)
于是可以同时除以GCD。
逆元是可以预处理的：
inv[P mod i]*(P mod i)=1 inv[p mod i]为逆元
inv[P mod i]*(P-P/i*i)=1
inv[P mod i]*i*(-P/i)=1
i*(P-P/i)*(inv[P mod i])=1 加粗的是逆元
一个重要性质 逆元是完全积性的！
【并没有卵用，直接筛就好啊！】
7 扩展欧几里得
用扩展欧几里得能做的 逆元也能做
ax+by=1 ->ax=1-by -> ax=1 mod p ->乘逆元c 这个也能反过来
ax+by=gcd(a,b)，若b=0，gcd(a,0)=a。原式变为ax+by==a -> x==1,y==0。
x,y表示第一次递归时的值，x1,y1表示第二次递归时的值。gcd(a,b)=gcd(b,a%b),同时都代入ax+by=gcd(a,b),出来ax+by=b*x1+(a%b)*y1。随便变形一下
b*x1+(a%b)*y1=
b*x1+(a-(a/b)*b)*y1= -》这里记住 a%b=a-floor(a/b)*b
a*y1+b*(x1-(a/b)*y1)=
ax+by==a*y1+b*(x1-(a/b)*y1)
也就是说，上一深度的x等于下一深度的y1，上一深度的y等于下一深度的x1-(a/b)*y1。
代码很短 也很好写 做的事情却很多
8 中国剩余定理
已知p1, p2, p3…pr两两互质
求x使得
x = a1 (mod p1)
x = a2 (mod p2)
…
x = ar (mod pr)
这玩意跟暴力一样23333
如果有一个x%p1 =a1 %p2=0 %p3=0 …【全是0】
如果找道%p1=a1 的x1 %p2= a2的…把他们全加起来，就是结果。
具体实现：
解x1的时候，用exgcd解 x1*p2*p3*p4*…=a1 mod p1
解x2的时候，用exgcd解 x2*p1*p3*p4*…=a2 mod p2
……..同理
这样乘上其他的就能保证mod其他的时候是0啦！
9 组合数取mod
1 暴力mod (暴力逆元）
2 mod p^t 的 记下来不互质的 最后再搞
3 mod非素数 拆成好多素数 然后套用2
4 Lucas定理
C(n,m)->把m，n转成p进制数,则c(n,m)=c(n1,m1)*c(n2,m2)*c(n3,m3)……
组合数统计：给定n, x, p，求C[n][i]=x (mod p)的i的数量
p是1000左右的质数， n <= 10^18
发现n很大 将组合数拆成·
c(n1,m1)*c(n2,m2)*c(n3,m3)……形式
则n已知 m未知 枚举m对n做背包
F[i][j]为前i个数 目前组合数mod p大小为j的数量
F[i][j]->f[i+1][j*c(ni,k)]
10 高斯消元取mod
交换两行 对能整除的部分进行相减 再交换两个 比较难懂
详见小Z的房间
11 离散模对数，原根，指标相关
离散对数：
给定x, z, P,求x^y = z (mod P) P是质数
a^x=b(mod n) => (a^m)^i*a^j=b(mod n) 由费马小定理 => a^j=b*v^i(mod n) 其中v为v=(a^m)^(p-1)
将a^j mod p存入hash(map)表
每次计算 b*v^i mod n,若计算过程中发现b*v^i mod n在hash 表中出现过,返回i*m+j
指数循环节：能使a^x=1 mod p 的x phi(p) 是一个指数循环节，但不一定是最小指数循环节
最小指数循环节即为指标-》一定为phi(p)的约数-》枚举phi(p)约数即可
指标恰好等于phi(p)的数，叫做原根，原根的幂可以遍历整个剩余系。
最小的原根为四次根号p级别 暴力枚举即可
有了原根就可以放心大胆取log啦！
给定y z p 求 x^y=z mod p：
找到p的原根g，两边同时对g取对数（g很小直接暴力取），变成y*logx=logz mod p-1 一定注意是p-1 然后exgcd搞一下
12 数论杂项
n=n所有的约数的欧拉函数之和=》解决gcd求和问题
还有奇葩的玩意我就不写了
13 组合与排列【DP与乱搞】
多重集排列：有N个元素 其中每个元素有ai个 则排列数为：N!/(a1!+a2!+a3!…)
容斥原理：总方案数好求，不满足A条件，不管B条件的方案数也好求，不满足B条件，不管A条件的方案数也好求，同时不满足AB条件的方案数也好求。则ans=总-不A-不B-不AB
其他类似，当有N个限制条件时，该式子有2^N项，注意时间复杂度。
此外还有数位统计？
14 概率相关
一个人抛硬币，抛到正面就睡觉，否则继续抛，求抛的次数的期望值：
设x为期望值
则x=(0*1/2+x*1/2)+1【抛到正面 直接睡觉，抛到反面，x次才能睡觉】一定要相信这个世界！
【题我就不说了 每个方程都比较鬼畜】
DAG随机游走-》直接dp
一般图随机游走-》有后效性-》高斯消元
没了吧！！！！比【我】较【会】重【了】要【的】的都说了吧！
应该会有好多错。。。问TZG好啦！