目录
一. 基本公式定理
1. 卢卡斯定理求大组合数
2. 中国剩余定理求同余方程
3. 费马大定理和勾股数
4. 费马小定理求逆元
5. 斯特林公式求高位乘阶
多项式化简6. 欧拉函数求1~n中与n互质的个数
7. 秦九昭算法化简多项式
8. 唯一分解定理
二. 素数相关
1. 素数筛法
三. 求解相关
1. 高斯消元法解线性方程组
2. 欧几里得和拓展欧几里得
四. 组合数学
1. 康拓展开和康拓逆展开
2. 关于逆元
3. 求组合数
五. 规律技巧
1. 快速幂
2. 快速乘
3. 和与三
4. 最大公约数和最小公倍数
4.1 求解代码
4.2 基本性质
六. 例题分析
1. 除法表达式
2. 求解模线性方程
3. UVA2719筛法求因数
七. 结尾与疑惑
1. 关于取余运算
2. 关于最大公约数和最小公倍数
应用要求：模数p为素数，且a与p互质即gcd（a,p）== 1
由费马小定理知：?a^(p-1) ≡ 1（mod p）即 a^（p-1）%p = 1
已知：a*inv（a）%p = 1
所以：a*inv（a）%p = a^（p-1）%p
则：inv（a）%p = a^（p-2）%p
????????于是这里用到快速幂 + 费马小定理来求逆元。
????????x^y%mod
????????(x*y)%mod
整数所有位置上数字之和若可以被3整除，则该整数可以被三整除。
4.1 求解代码
4.2 基本性质
设：A = (x1^p1)*(x2^p2)*(x3^p3)*......
? ? ? ?B = (x1^q1)*(x2^q2)*(x3^q3)*......
则：LCM(A,B) = x1^max(p1,q1) * x2^max(p2,q2) * x3^max(p3,q3) * .......（最大部分）
? ? ? ?GCD(A,B) = x1^min(p1,q1) * x2^min(p2,q2) * x3^min(p3,q3) * ......(共有部分)
（1）若给出G,L，求出a,b，以G为最大公约数，以L为最小公倍数，若存在求出a最小的正整数解，不存在输出-1（UVA11388）
设：a = k1*G , b = k2*G
则由最大公因数和最小公倍数关系：a*b = G*L
即k1*k2*G*G = G*L
即L = k1*k2*G? 因为k1,k2均为正整数，所以有解的条件是：?L%G==0
此时：a = k1*G , b = L/k1? ?所以a最小时k1 = 1
则最小解：a = G, b = L，证毕。
（2）给出A,C，已知LCM(A,B) = C，求出最小正整数B，若不存在输出NO SOLUTION? (UVA11889)
已知：A*B = C*GCD(A,B)
则：B = C/A*GCD(A,B)
此时可以：枚举A的因子i，判断GCD(A,B)是否==i ，从而找到最小解
除此之外：LCM(A,B) = x^p1 * y^p2 * z^p3 *.......
? ? ? ? ? ? ? ? ?GCD(A,B) = x^q1 * y ^q2 * z^q3 * ......
? ? ? ? ? ? ? ? ?A = x^m1 * y^m2 * z^m3 * ......
?多项式化简 ? ? ? ? ? ? ? ?B = x^n1 * y^n2 * z^n3 *......
? ? ? ? ? ? ? ? ?B' = C/A = B/GCD(A,B) = x^k1 * y^k2 * z^k3 * ....
其中： p1 = max(m1,n1) , p2 = max(m2,n2) , .....
? ? ? ? ? ? q1 = min(m1,n1) , q2 = min(m2,n2) , .......
? ? ? ? ? ? k1 = n1 - q1 , k2 = n2 - q2
? ? ? ? 由上可知，如果GCD(A,B)==1，则B = C/A；现在思考怎么把B'变成B，因为手上只有A和B'可以直接用，所以考虑x^m1与x^k1：
- 如果x^m1与x^k1最大公约数为1，那就说明m1==0或者k1==0
????????若m1==0：q1 = m1 = 0,则k1 = n1与B的系数相同了，变过来了，不用继续变下去了；若k1==0：n1 = q1，又因为q1 = min(m1,n1) ，?所以n1<=m1 ，?所以此时n1=0 = k1符合题意，变过来了。
????????所以当GCD(A,B')==1时说明，每一个对应项都达到了上述变成了B的效果，就说明B'变成了B。
- 如果x^m1与x^k1最大公约数不为1 ，?那就说明m1!=0&&k1!=0
? ? ? ? 则 n1 = k1+q1：n1 = k1+min(m1,n1)? ? 所以一定是m1<=n1；所以k1 = n1 - m1(B'的系数)? ?那么怎么把k1变成n1呢？就是给每一个没变过来的乘上A的系数。这里采取：
int g = GCD(A,B')（不断取公共部分）；
B'*=g；
A/=G；
????????这三行代码最终一定能把n1-m1 ----> n1 ，?而A中相应系数变为0，最终实现代码如下：
Problem Description
给出一个这样的除法表达式：X1/X2/X3/···/Xk，其中Xi是正整数。除法表达式应当按照从左到右的顺序求解，例如表达式1/2/1/2的值为1/4。但是可以在表达式中嵌入括号以改变计算顺序，例如表达式(1/2)/(1/2)的值为1.
INPUT
首先输入一个T，表示有T组测试数据，
每组数据输入占一行，第一个数字为k，后面跟k个数字为一个除法表达式，
输入保证合法。
判断能否使表达式的值为整数。k<=10000,Xi<=100000000.OUTPUT
输出YES或NO
????????表达式的值一定可以写成A/B的形式。假设表达式为整数，A=xp1*xp2*xp3*xp4*....*xpk；假设B=xq1*xq2*xq3*.....*xqn；因为A/B为整数，则A为xq1*xq2*xq3*....*xqn的倍数，那么A肯定也是xq1的倍数，是xq2的倍数...，那么(A/xq1 )*xq2*xq3*.....*xqn一定也是整数。
????????所以不管怎样，表达式都能化成分母只有一个因子的样子，而我们发现，X2是一定位于分母上的！所以最终我们只需要判断X1*X3*X4*.....*Xk/X2是否为整数即可判断整个表达式！
基本概念
求解满足ax≡b(mod n)的所有x的过程，叫做解模线性方程。
即 ax%n = b%n
即 ax + ny = b
即求解拓展欧几里得的x
性质：
（1）当a-b可以整除n时，方程才有解
（2）当b%gcd(a,n)==0时，方程才有解
（3）根据完全剩余系，方程有gcd(a,n)个解，x = x0 + i*(b/gcd(a,n))(i = 0,1,2.....gcd(a,n)-1),存在最小正整数解
注意：当b==1时，ax≡1(mod n)
此时：方程具有惟一最小正整数解，只有gcd(a,n)==1时有解也就是要求a,n互质
此时：解x称为a关于n的逆元?x = inv(a,n)
求逆元方法有：费马小定理/拓展欧几里得
Problem Description
求n以内所有满足，GCD(A,B) = A^B的数字对数
? ? ? ? 因为有异或性质：A^B = GCD多项式化简(A,B) = C，则C = A - B；则筛出A的所有因数C，B = A - C ,?判断A^B是否==C即可。由于因数C可能会被重复枚举，所以直接枚举因数C，枚举到n/2。
????????每一对取余运算都会产生两个结果即正负模数。这两个结果是通过两种运算规则产生的，正负模数可以互相转化，虽然数值不等，但是在运算本质上都是对的。
关系：“整除是数学中两个自然数(不包括0）之间的一种关系.”
概念：“整除是指整数a除以自然数b（b≠0）除得的商正好是整数而余数是零．我们就说a能被b整除”?
定义：“对自然数a,b（b≠0）,若存在自然数c,使a＝bc,则称b整除a”
????????约数是在整除基础上建立起来的概念，所以，负数并不存在最大公约数和最小公倍数的概念，所以，最大公约数和最小公倍数为自然数。
