class="markdown_views prism-github-gist">

• • • • • • p.s 还未完成
• 最大公约数和最小公倍数
• 欧几里得算法
  • • • • • 即辗转相除法
• 唯一分解定理
• 质数
• 同余
• 剩余系
• 威尔逊定理
• 费马小定理
• 欧拉函数
• 扩展欧几里得算法
  • • 说明
    • 代码
    • 应用
• 模线性方程组
  • 中国剩余定理
• 逆元
• 加法原理
• 乘法原理
• 排列组合
• 第一类Stirling数
• 第二类Stirling数
• 阶
• 原根
• 离散对数

p.s 还未完成

最大公约数和最小公倍数

1.最大公约数 gcd
2.最小公倍数 lcm
3.定理
gcd(a,b)*lcm(a,b)=a*b

欧几里得算法

即辗转相除法

gcd(a,b)=gcd(b,a%b)
性质：
若a,b为偶数，则gcd(a,b)=2*gcd(a/2,b/2)
若a偶b奇，则gcd(a,b)=gcd(a/2,b)

唯一分解定理

任意一个大于1的整数n，均可以表示为若干
个素数的乘积，且这个形式是唯一的。
n=p1m1*p2m2*……pkmk
其中,p1,p2,……pk 为n的质因子。

质数

因数只有1和本身的数（1不是质数）
判断质数方法 int prime[MAXP]; bool flag[MAXN]; int j=0; for(int i=2;i<=n;i++) { if(flag[i]==0) prime[j++]=i; for(int k=0;kif(prime[k]*i>n)break; flag[prime[k]*i]=1; if(i%prime[k]==0)break; } } 除此之外，还有一种比较神奇的做法：Miller-Rabbin测试
http://blog.csdn.net/sluqy671/article/details/41701655

同余

若a%m=b%m,则称a与B关于模m同余，记为 a≡b(mod m)" role="presentation" style="text-align: center; position: relative;">a≡b(mod m)$$a\equiv b(modm)$$
性质：
1.自反性： a≡a(mod m)
2.对称性：若 a≡b(mod m)，则 b≡a(mod m)
3.传递性：若a≡b(mod m)，b≡c(mod m)，则 a≡c(mod m)
4.同加性：若a≡b(mod m)，则a+c≡b+c(mod m)
5.同乘性：若a≡b(mod m)，则a*c≡b*c(mod m)
若a≡b(mod m),c≡d(mod m),则有a*c≡b*d(mod m)
6.同幂性：若a≡b(mod m)，则a的n次方≡b的n次方(mod m)
7.若a%p=x,a%q=x,且p,q互质，则a%(p*q)=x
mod运算中加、减、乘均满足分配律，然而除法没有分配律

剩余系

给定n，则所有整数对n取模，将得到一个集合，称为模n的剩余系，即{0,1,2,……,n-1}。
n的剩余系中与n互质的数称为简化剩余系，也称为缩系。n的剩余系记为Zn，而n的缩系记为Zn*.
模n的剩余系中，每个元素都代表所有与它同余的整数，比如n=7，则1代表{1,8,15,22,……}，这个集合满足模n同余关系，称为同余等价类。
剩余系相关定理 1.若a，b互质，则存在一个整数k＜b，使得a*k%b=1 2.若a，b互质，则b的缩系中的元素乘以a再模b，仍然得到缩系中的元素所有元素。 3.若a，b互质，则c1=k1*a,c2=k2*a,若c1%b==c2%b,则必有k1%b==k2%b。(因子与模数互质，等式两边可以消去因子。) 4.对于任意正整数n，n的缩系中的元素的乘积模n要么等于1，要么等于n-1。(根据1和2可证)

威尔逊定理

若p为素数，则(p-1)!≡-1(mod p)。 其逆定理也成立。 证明：对于p的缩系中的任何一个元素，必存在一个唯一的元素与之配对，使得其乘积为1。
只有1和p-1是自己和自己配对，其他都是两两配对。
所以得证。
若p为合数，则(p-1)!与p必定不互质，所以(p-1)!%p不可能等于-1。（模p时-1即为p-1，而p-1与p是互质的。）
所以其逆定理得证。

费马小定理

若P为素数，a为正整数，且a和P互质，则有： ap-1≡1(mod p) 证明：只需证明ap-1(p-1)!=(p-1)!(mod p)即可。
根据剩余系相关定理2，即可证明。

欧拉函数

欧拉函数φ ：不超过n的且与n互质的正整数的个数。
如果n为素数p，则φ(p)=p-1
如果n为素数p的幂次pa，则φ(pa)=(p-1)*pa-1.
欧拉函数为积性函数：如果n为任意两个互质的数a、b的积，则 φ(n)= φ(a)*φ(b)
若n=p1a1*p2a2*……*pkak （本来想打p1的a1次方，将就着看吧）
则φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pk)
欧拉定理：
若a与m互质，则aϕ(m)≡1(mod m)" role="presentation" style="text-align: center; position: relative;">aϕ(m)≡1(mod m)$$a^{\varphi (m)}\equiv 1(modm)$$
证明：将等式两边乘上缩系中所有元素的乘积，根据引理2即可得证。

扩展欧几里得算法

说明

对于任意整数a，b，一定存在整数x、y，使得ax+by=gcd(a,b)
若gcd(a,b)=1,则一定存在整数x，y，使得ax+by=1
可以使用扩展欧几里德算法求出x，y。
因为ax+by=gcd(a,b)=gcd(b,a%b)=bx’+(a%b)*y’
所以ax+by=bx’+(a-a/b*b)y’
因为上式对于任意a，b（b!=0）都成立，所以可以将a，b看做变量，将x，y，x’,y’等看做系数。左边a的系数应该等于右边a的系数，所以x=y’
左边b的系数应该等于右边b的系数，所以y=x’-(a/b)*y’
可以递归下去，直到a%b=0时，可求得x’=1,y’=0,然后层层返回即可求出原来的x和y。

代码

void gcd(LL a,LL b,LL &d,LL &x,LL &y) { if(!b){x=1;d=a;y=0;} else { gcd(b,a%b,d,y,x); y-=x*(a/b); } } //x即为a关于模b的逆元

应用

1.求二元一次方程：ax+by=c
2.求模线性方程：ax≡b (mod n)
3.求逆元：ab≡1 (mod n)
4.求gcd(a,b)

模线性方程组

x≡b1 (mod n1)
x≡b2 (mod n2)
……
x≡bk (mod nk)
其中n1，n2，……，nk互质。
这样的方程组称为模线性方程组

中国剩余定理

中国剩余定理就是用来解模线性方程组的
对于n1，因为它与(n2n3……nk)互质，我们可以找到一个系数z1，使得z1n2n3……nk%n1=1。设z1n2n3……nk为c1.
同理，对于每个nk，都可以找到一个zi，使得（zin1n2……nj|j!=i)%ni=1，设（zin1n2……nj|j!=i)为ci
则x=b1*c1+b2*c2+……bk*ck+m(n1*n2*…*nk) 其中m为任意整数。
x为一组解

逆元

如果(ab)%n=1,则a、b互为对方关于模n的逆元。
若a是b关于模n的逆元，则(c/b)%n=(ca)%n=(c%n)(a%n),由此可弥补除法没有分配律的缺陷。
若a与n互质，则必存在一个整数b，使得a*b%n=1,即a模n的逆元一定存在。
若b存在逆元，则有(a/b)%n=(a*b-1)%n。
证明：设b的逆元为c，则bc%n=1
(a/b)%n=((a/b)bc)%n=ac%n=ab-1%n

加法原理

略，请自行百度

乘法原理

略，请自行百度

排列组合

从n个数中取出k个数并进行无重排列的总数，得到的就是排列数
记为A(n,k)或P(n,k)
从n个数中取出k个数的方案数，得到的就是组合数
组合数有如下性质 性质1：C(n,0)=1 性质2：C(n,k)=C(n,n-k) 性质3：C(n,k)+C(n,k+1)=C(n+1,k+1)//所以可以用来递推求组合数

第一类Stirling数

第一类Stirling数表示表示将 n 个不同元素构成m个圆排列的数目
考虑其定义:如果要将n+1元素构成m个圆排列，考虑第n+1个元素：
（1）如果n个元素构成了m-1个圆排列，那么第n+1个元素独自构成一个圆排列。方案数：s(n,m-1)
（2）如果n个元素构成了m个圆排列，将第n+1个元素插入到任意元素的左边。方案数：n*s(n,m)
综上， s(n+1,m)=s(n,m-1)+n*s(n,m)

第二类Stirling数

第二类Stirling数实际上是集合的一个拆分，表示将n个不同的元素拆分成m个集合的方案数
考虑第n+1个元素：
（1）如果n个元素构成了m-1个集合，那么第n+1个元素单独构成一个集合。方案数S(n,m-1)。
（2）如果n个元素已经构成了m个集合，将第n+1个元素插入到任意一个集合。方案数 m*S(n,m) 。
综上， S(n+1,m)=S(n,m-1)+m*S(n,m)

阶

由欧拉定理可得
若a∈Z,m∈Z+" role="presentation" style="position: relative;">a∈Z,m∈Z+$a\in Z,m\in Z^{+}$且(a,m)=1,则aϕ(m)≡1(mod m)" role="presentation" style="position: relative;">aϕ(m)≡1(mod m)$a^{\varphi (m)}\equiv 1(modm)$
然后可以有以下定义
a∈Z,m∈Z+" role="presentation" style="position: relative;">a∈Z,m∈Z+$a\in Z,m\in Z^{+}$ 且(a,m)=1,如果l是使al≡1(mod m)" role="presentation" style="position: relative;">al≡1(mod m)$a^l\equiv 1(modm)$成立的最小正整数,则称l为a关于模m的阶,记为ordma" role="presentation" style="position: relative;">ordma$or{d}_{m}a$

除此之外关于阶还有一些定理

定理1
设ordma=l" role="presentation" style="position: relative;">ordma=l$or{d}_{m}a=l$,整数n≥0" role="presentation" style="position: relative;">n≥0$n\ge 0$,则an≡1(mod m)" role="presentation" style="position: relative;">an≡1(mod m)$a^n\equiv 1(modm)$当且仅当l∣n" role="presentation" style="position: relative;">l∣n$l\mid n$.特别地,l∣ϕ(m)" role="presentation" style="position: relative;">l∣ϕ(m)$l\mid \varphi (m)$
定理2
设ordma=l" role="presentation" style="position: relative;">ordma=l$or{d}_{m}a=l$,i和j为非负整数,则ai≡aj(mod m)" role="presentation" style="position: relative;">ai≡aj(mod m)$a^i\equiv a^j(modm)$当且仅当i≡j(mod m)" role="presentation" style="position: relative;">i≡j(mod m)$i\equiv j(modm)$
推论1
设ordma=l," role="presentation" style="position: relative;">ordma=l,$or{d}_{m}a=l,$则1,a,a2,⋯,al−1" role="presentation" style="position: relative;">1,a,a2,⋯,al−1$1,a,a^2,\cdots ,a^{l-1}$关于模m两两互不同余
定理3
如果ordma=l,s∈Z+" role="presentation" style="position: relative;">ordma=l,s∈Z+$or{d}_{m}a=l,s\in Z^{+}$那么,ordmas=l(s,l)" role="presentation" style="position: relative;">ordmas=l(s,l)${or{d}_{m}a}^s=\frac{l}{(s,l)}$
推论2
设