#数论个人总结三-个人总结
i207M
·
·
个人记录
一些递归式子
A(i,j)=A(i-1,j-1)+A(i-1,j)\to A(i,j)=C^j_i\times A(0,0)
A(i,j)=A(i-1,j+1)+A(i-1,j)\to A(i,j)=\sum \limits_{k=0}^iC_i^k \times A(0,j+k)
人人尽说江南好
有N堆石子，最初每堆为1；每次可以合并两堆石子，当且仅当合并后大小<=M，不能行动者输，问输赢？
最终形成的石子一定是m,m,\dots ,n \mod m，这样，最终石子的堆数确定，每次合并堆数-1，合并数也确定；根据奇偶性得出答案；
exgcd的计算过程最大数字（要先除再乘）不超过最大值的2倍
中国剩余定理证明\phi是积性函数
当x=p^k，答案为p^k-p^{k-1}，因为p^k之内含有因数p的数字有p^{k-1}个；所以当x=p^k时，\phi (x)=(p-1)\times p^{k-1}；
当x=p_1^{k_1}p_2^{k_2}，因为gcd(n,ab)==1等价于gcd(n,a)==1\& \&gcd(n,b)==1
满足第一个条件的数字有\phi(p_1^{k_1})，第二个有\phi(p_2^{k_2})，而已知y \mod a=c\& \& y \mod b=d,gcd(a,b)==1，则y可以唯一对应一个0\to ab-1的一个数，也就是\phi(p_1^{k_1}p_2^{k_2})；
预处理标准分解N<=10^7
预处理出每个数的mindiv，直接除；
组合数前缀和的公式
设S(n,m)=\sum\limits_{i=0}^mC_n^i，则有递推式：
## 范德蒙德卷积
证明第二个通过组合意义；
证明第一个（第三个同理）：$\sum \limits_{i=1}^n C^i_nC^{m-i}_m
\sum\limits_{i=1}^n iC^i_n=\sum\limits_{i=1}^n \frac{n!}{(i-1)!(n-i)!}=n\sum\limits_{i=1}^n \frac{(n-1)!}{(i-1)!(n-i)!}=n\sum\limits_{i=1}^n C^{i-1}_{n-1}=n2^{n-1}
移动\sum \Pi 时，要注意顺序
高维前缀和与高维差分
前缀和，就是yzh讲的那道牛客题；
高位差分，就是把前缀和恢复为原数组，方法和前缀和差不多；
[SDOI2008]沙拉公主的困惑
求[1,n!]中与m!(n>=m)互质的数的个数；
当n==m时，答案显然是\phi(m!)
其他情况，考虑：gcd(a,b)=1 \to gcd(a+kb,b)=1
对于[1,m!]中与m!互质的数，将它们加上m!后依然互质，所以每m!个循环一次，答案即为n!/m!\times \phi(m!)=n!\times ...
阶乘
(p - 2)! = 1 \mod p
(p-1)!+(p-2)!=p(p-2)! =0\mod p
（感叹号！是阶乘的含义）
一式的证明：p是质数，所以除了1的逆元是1，p-1的逆元是p-1。其余的逆元都可以一一配对，所以乘起来为p-1；
递推阶乘的乘法逆元时，要先求逆元，再前缀乘起来
Farey序列
将0到1中分母不大于n的最简分数，从小到大排列成的数列即为n阶farey序列，性质：对于farey序列中的相邻的两个分数c/a,d/b，有ad-bc=1
第二类斯特林数
S_n^m=\frac1{m!}\sum_{i=0}^m(-1)^i{m\choose i}(m-i)^n=\sum_{i=0}^m\frac{(-1)^i}{i!}\frac{(m-i)^n}{(m-i)!}
下降幂
x^{\underline{n}} = \frac{x!}{(x-n)!}
化简式子的Trick
如果其中包含斯特林数，尝试用n^k代替。如果其中包含n^k，尝试用斯特林数代替。
化简C^j_i\times C^k_j的思路：
考虑和C^k_i有什么联系：相当于先选择j个，再从j个里选k个，所以有多少个包含k的集合，就有几种方案，所以答案为C^k_i\times 2^{i-k}
多项式的次数
k阶差分
给定若干个数，和为N，则里面不同的数字最多有\sqrt{N}种
异或的前缀和
1...2n-1的连续奇数异或和：
n%4...0: 0
1: 2n-1
2: 2
3: 2n+1
2...2n的连续偶数异或和：
n%4...0: 2n
1: 2
2: 2n+2
3: 0
1...n的连续数字异或和：
n%4...0: n
1: 1
2: n+1
3: 0
每列组合数每隔两个的和
可以忽略之前m的定义。
小技巧：\max(a,b)=(a+b+|a-b|)/2
GCD问题，如果数据范围较小，可以枚举一个数的所有因数
每行每列和均为0的矩阵行列式为0
\phi(ab)=\phi(a)\phi(b)g/\phi(g),g=\gcd(a,b)
概率&积分
给定长度为L的棍子，每次随机一个位置截断，只留下右边，当长度\le d时结束，问期望次数。
可以列出方程：
f(x)=1+1/x\int_0^xf(x)dx
取整除法的转化
ceil(a/b)=floor((a-1)/b)+1
给定 L,R,k，询问本质不同的数字 x 的个数，使得存在 L≤a1,a2,…,ak≤R ，并且 gcd(a1,a2,…,ak)=x 。
首先注意到，k只有=1或>1两种有用的状态。然后一个数存在当且仅当x\in [L,R]或x在[L,R]中出现两次，发现出现次数是r/x-(l-1)/x，于是可以整除分块做。
n个点的无向完全图，走k步从1到1的方案数
f(n,k)=\frac{(n-1)^k+(n-1)(-1)^k}{n}
这份代码也是对的。
for(ri i=1; i<=10; ++i)
{
mem(f,0); f[0]=1;
for(ri j=2; j<=10; ++j)
{
for(ri k=0; k<=j-2; ++k)
inc(f[j],mul(f[k],mul(i-1,qpow(i-2,j-k-2))));
out(f[j]),space;
}
enter;
}
G(i)=(n-2)^i
F=(n-1)FGx^2+1
F=\frac{1}{1-(n-1)Gx^2}
求形如x^k
如果直接算不好求，尝试斯特林展开，或者计算x^{\underline{k}}，然后组合数回去。
SPERNER定理
有一个n元集合S_n，从中选出若干个子集，满足没有任何两个子集之间存在包含关系，问最多能选出多少个？
答案是n\choose [n/2]，下界好说，上界在这
Min-Max容斥第k大
BSGS记得特判b=1的情况
杜教筛求多次，保证复杂度的话，不能用数组记忆化， 必须用(unordered_)map
Koishi Loves Number Theory
重要的性质：
gcd(x^n-1,x^m-1)=x^{\gcd(n,m)}-1
于是求lcm可以用minmax反演。
上取整整除分块
ceil(n/x)=floor((n-1)/x)+1
拆卷积
ab={a+b\choose 2}-{a \choose 2}-{b\choose 2}
离线O(n)求逆元
类似求阶乘逆元的方法，我们先求出\prod a_i的逆元，然后乘以a_i的前缀和/后缀和即可。
光速幂，任意底数任意指数
先求原根，然后变成求原根的若干次方。
Atcoder某题
求\prod_{i=0}^{n-1} (x+id)\mod p
我们会求\prod (x+i)，那全部除以d，不就变成\prod (x/d+i)，然后预处理一下阶乘就可以了。
树的邻接矩阵的秩等于最大匹配数×2
矩阵费马小定理
形如f_i=af_{i-1}+b的矩阵是有费马小定理的，但当a=1时，循环节为p。
常用的因式分解技巧
\prod_{i=1}^{p-1} (x+i)=x^{p-1}-1\mod p
（p是质数）
\prod (x-w_n^i)=x^n-1
期望
E(f(x))=\sum_i^{\infty}f'(i)P(x\ge i)dx
神奇的斯特林式子
感性理解的证明：
n+1号点所在环的点的集合固定了，假设大小为m，就有(m-1)!种，然后重新理解成去掉n+1 原先环上的点可以任意排成若干个环，其余的有k个环，求方案数，然后就和左边的一样了。（这个证明有一个问题，没有给出新环的一一对应的构造方法）
L群里神仙的解法：
证明在下一道题。
Topcoder CyclesNumber
哇塞，神仙生成函数！
首先，我们要求的式子是
\sum_iS_1(n,i)i^m
把i^m展开：
\sum_iS_1(n,i)\sum_j^iS_2(m,j)i^{\underline j}
移项：
\sum_j^mS_2(m,j)\sum_{i=j}^nS_1(n,i)i^{\underline j}
重头戏来了：注意到（f^{(j)}表示对f求j阶导）
(x^n)^{(j)}=x^{n-j}n^{\underline j}
因此，\sum_iS_1(n,i)i^{\underline j}相当于把s_n(x)求j阶导后代入x=1！
代入x=1比较麻烦，我们设g(x)=s_n(x+1)，则
g(x)=(x+1)^{\overline{n}}=x^{\overline {n+1}}/x
于是g_i=S_1(n+1,i+1)
联系上文式子
另一种拆法：
g(x)=\sum_j^nx^j\sum_iS_1(n,i){i\choose j}
由对应关系可得
\sum_iS_1(n,i){i\choose j}=S_1(n+1,j+1)
代入x=0相当于是求j阶导后的常数项，也就是S_1(n+1,j+1)j!
于是O(nm)递推斯特林数即可。
关键在于把i^{\underline j}联想到求导，以及上升幂的灵活转化
莫比乌斯反演小技巧
如何求\sum_if(2i)（f是积性函数）
注意到g(i)=[i\mod 2=1]是完全积性函数，我们只需要求出\sum_i f(i)和\sum_i f(i)g(i)即可，积性函数前缀和可以直接min_25。
如果用杜教筛的话，(f·g)*g=g·(f*1)，如果f=\varphi可以很方便的求了。
简单的求自然数幂和的方法
\sum_{i=1}^n i^k=\sum_{i=1}^n \sum_jS_2(k,j)j!{i\choose j}
=\sum_{j=1}^{\min(n,k)} S_2(k,j)j!{n+1\choose j+1}=\sum_{j=1}^{\min(n,k)} S_2(k,j)(n+1)^{\underline{j+1}}/(j+1)
需要O(k^2)/O(k\log k)求斯特林数。
下取整的上下界
n/i=x,i\in [n/(x+1)+1,n/x]
乘积平方数
两个数乘起来是平方数，当且仅当把两数分解为a^2b的形式，其中b不含非平凡平方因子（|\mu(b)|=1）后b相等。
自然数幂和
瞎写的理性愉悦：正整数幂和与伯努利数