- 排列的定义:从n个不同元素中,任取m(m≤n,m与n均为自然数)个不同的元素按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列,从n个不同元素中取出m(m≤n)个元素的所有排列的个数,叫做从n个不同元素中取出m个元素的排列数,用符号
A
(
n
,
m
)
A(n,m)
A(n,m)或
A
n
m
A_n^m
Anm表示。
A ( n , m ) = n ∗ ( n − 1 ) ∗ ( n − 2 ) ∗ . . . ∗ ( n − m + 1 ) = n ! ( n − m ) ! A(n,m)=n* (n-1) * (n-2)* ... * (n-m+1)=frac{n!}{(n-m)!} A(n,m)=n∗(n−1)∗(n−2)∗...∗(n−m+1)=(n−m)!n!
- 从n个不同元素中,任取m(m≤n)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合,从n个不同元素中取出m(m≤n)个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数。用符号
C
(
n
,
m
)
C(n,m)
C(n,m)或
C
n
m
C_n^m
Cnm 表示。
C ( n , m ) = A ( n , m ) m ! = n ! ( n − m ) ! m ! C(n,m)=frac{A(n,m)}{m!}=frac{n!}{(n-m)!m!} C(n,m)=m!A(n,m)=(n−m)!m!n! - C ( n , m ) = C ( n , m − 1 ) + C ( n − 1 , m − 1 ) C(n,m)=C(n,m-1)+C(n-1,m-1) C(n,m)=C(n,m−1)+C(n−1,m−1)
- C ( n , m ) = C ( n , n − m ) C(n,m)=C(n,n-m) C(n,m)=C(n,n−m)
- ∑ i = 0 n C ( n , i ) = 2 n sum_{i=0}^{n}C(n,i)=2^n ∑i=0nC(n,i)=2n
- C ( n , 0 ) − C ( n , 1 ) + . . . ± C ( n , n ) = 0 C(n,0)-C(n,1)+...pm C(n,n)=0 C(n,0)−C(n,1)+...±C(n,n)=0
- C ( n , 0 ) + C ( n , 2 ) + C ( n , 4 ) + . . . = C ( n , 1 ) + C ( n , 3 ) + C ( n , 5 ) + . . . = 2 m − 1 C(n,0)+C(n,2)+C(n,4)+...=C(n,1)+C(n,3)+C(n,5)+...=2^{m-1} C(n,0)+C(n,2)+C(n,4)+...=C(n,1)+C(n,3)+C(n,5)+...=2m−1
- p 是 素 数 , C ( n , m ) % p = C ( n / p , m / p ) ∗ C ( n % p , m % p ) % p p是素数,C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p p是素数,C(n,m)%p=C(n/p,m/p)∗C(n%p,m%p)%p
加法递推
- 动态规划的思想, C ( n , m ) = C ( n − 1 , m − 1 ) + C ( n − 1 , m ) , C ( n , 0 ) = 1 C(n,m)=C(n-1,m-1)+C(n-1,m),C(n,0)=1 C(n,m)=C(n−1,m−1)+C(n−1,m),C(n,0)=1,复杂度为 O ( n 2 ) O(n^2) O(n2)
for(int i=0;i<=n;i++){
C[i][0]=1;
for(int j=1;j<=i;j++){
C[i][j]=C[i-1][j-1]+C[i-1][j];
}
}
乘法递推
- C ( n , m ) = n − m + 1 m C ( n , m − 1 ) , C ( n , 0 ) = 1 C(n,m)=frac{n-m+1}{m}C(n,m-1),C(n,0)=1 C(n,m)=mn−m+1C(n,m−1),C(n,0)=1,复杂度为 O ( n ) O(n) O(n)
C[0]=1;
if(m>n-m) m=n-m;
for(int i=1;i<=m;i++){
C[i]=(n-i+1)*C[i-1]/i;
}
整除性质
- a ∣ b ↔ − a ∣ b ↔ ∣ a ∣ ∣ ∣ b ∣ a|bleftrightarrow-a|bleftrightarrow|a| | |b| a∣b↔−a∣b↔∣a∣ ∣ ∣b∣
- a ∣ b , b ∣ c → a ∣ c a|b,b|crightarrow a|c a∣b,b∣c→a∣c
- a ∣ b , a ∣ c → a ∣ ( b x + c y ) , x , y , ∈ N a|b,a|crightarrow a|(bx+cy),x,y,in{N} a∣b,a∣c→a∣(bx+cy),x,y,∈N
- KaTeX parse error: Undefined control sequence: and at position 30: … am|bm,min{N} ̲a̲n̲d̲ ̲m ne 0
- KaTeX parse error: Undefined control sequence: abs at position 21: …|a rightarrow ̲a̲b̲s̲{a}=abs{b}
- a ∣ b c g c d ( a , c ) = 1 → a ∣ b a|bc gcd(a,c)=1rightarrow a|b a∣bc gcd(a,c)=1→a∣b
- a ∣ b , a ∣ c , g c d ( b , c ) = 1 → a ∣ b c a|b,a|c,gcd(b,c)=1rightarrow a|bc a∣b,a∣c,gcd(b,c)=1→a∣bc
- a ∣ b , c ∈ N → b ∣ a c a|b,cin{N}rightarrow b|ac a∣b,c∈N→b∣ac
- 带余除法定理:
∀
a
,
b
>
0
,
∃
唯
一
q
,
r
使
得
a
=
b
q
+
r
,
其
中
0
≤
r
<
b
forall a,b>0,exists 唯一q,r使得a=bq+r,其中0le r0,∃唯一q,r使得a=bq+r,其中0≤r
- ( a ± b ) % p = ( a % p ± b % p ) % p (apm b)%p=(a%ppm b%p)%p (a±b)%p=(a%p±b%p)%p
- ( a ∗ b ) % p = ( ( a % p ) ∗ ( b % p ) ) % p (a*b)%p=((a%p)*(b%p))%p (a∗b)%p=((a%p)∗(b%p))%p
- ( a b ) % p = ( ( a % p ) b ) % p (a^b)%p=((a%p)^b)%p (ab)%p=((a%p)b)%p
- 模运算满足结合律,交换律和分配律
- 反身性: a ≡ a ( m o d m ) aequiv a(mod m) a≡a(mod m)
- 对称性: a ≡ b ( m o d m ) → b ≡ a ( m o d m ) aequiv b(mod m)rightarrow bequiv a(mod m) a≡b(mod m)→b≡a(mod m)
- 传递性: a ≡ b ( m o d m ) , b ≡ c ( m o d m ) → a ≡ c ( m o d m ) aequiv b(mod m),bequiv c(mod m)rightarrow aequiv c(mod m) a≡b(mod m),b≡c(mod m)→a≡c(mod m)
- 同余相加: a ≡ b ( m o d m ) , c ≡ d ( m o d m ) → a + c ≡ b + d ( m o d m ) aequiv b(mod m),cequiv d(mod m)rightarrow a+cequiv b+d(mod m) a≡b(mod m),c≡d(mod m)→a+c≡b+d(mod m)
- 同余相乘: a ≡ b ( m o d m ) , c ≡ d ( m o d m ) → a ∗ c ≡ b ∗ d ( m o d m ) aequiv b(mod m),cequiv d(mod m)rightarrow a*cequiv b*d(mod m) a≡b(mod m),c≡d(mod m)→a∗c≡b∗d(mod m)
真因子之和等于它本身的自然数
高效打表
本题可以转化为对每个数求真因子之和，其算法如下
- 所有数都含有真因数 1 1 1,初始化所有数的因子和为 1 1 1( 0 , 1 0,1 0,1除外)
- 循环 i i i从 2 2 2开始,到打表上限
- 让 j = 2 i , 3 i , 4 i , . . . . j=2i,3i,4i,.... j=2i,3i,4i,...., j < = 上 限 j<=上限 j<=上限
- 说明所有的 j j j都含有真因数 i i i,对应因数和就要加上 i i i
- 这个数因数和等于这个数,说明是完全数
long long num[N];
void init(){
for(int i=2;i
素数
只能被1和自身整除的数就是素数。
反素数
记正整数
x
x
x的因数个数为
g
(
x
)
g(x)
g(x)，如
g
(
1
)
=
1
,
g
(
6
)
=
4
g(1)=1,g(6)=4
g(1)=1,g(6)=4
如果正整数
x
x
x满足：对于任意
i
∈
N
+
,
0
<
i
<
x
iin N^+,0
g
(
i
)
,
则
称
g(x)>g(i),则称
g(x)>g(i),则称x$为反素数。
性质
- 反素数的素因子必然是从2开始连续的素数
-
x
=
p
1
a
1
∗
p
2
a
2
∗
⋯
∗
p
n
a
n
x=p_1^{a_1} *p_2^{a_2} *dots*p_n^{a_n}
x=p1a1∗p2a2∗⋯∗pnan，必然有
a
1
≥
a
2
≥
a
3
≥
⋯
≥
a
n
a_1ge a_2ge a_3ge dots ge a_n
a1≥a2≥a3≥⋯≥an
- 反素数是区间内因子最多的数，因子数相同的数中，反素数值最小
素数判定
试除法
尝试
2
∼
s
q
r
t
(
n
)
2sim sqrt(n)
2∼sqrt(n)能不能整除
n
n
n
int prime(int n){
if(n==2) return 1;//2是素数
if(n<=1||n%2==0) return 0;//1和其余偶数不管
for(int i=3;i*i<=n;i+=2){//只在奇数中循环
if(n%i==0) return 0;
}
return 1;
}
埃氏筛法
伪代码
for(i=2;i<=上界;i++){
for(j=i+i;j<=上界;j++){//标记i的倍数为非素数
标记j为非素数
}
}
C++代码
int isPrime[N+1];//判断素数
void init(){
isPrime[0]=isPrime[1]=0;//标记0 1不是素数
for(int i=2;i<=N;i++){
if(!isPrime[i]) continue;//非素数继续下一轮
for(int j=i+i;j<=N;j+=i){
isPrime[j]=0;//标记i的倍数不是素数
}
}
}
欧拉筛法(线筛法)
把所有已经找到的素数倍数筛为合数，是埃氏筛法的改进版，不会重复筛选
int isPrime[N+1];//判断素数
int primes[N/2+1];//存素数
int cnt=0;//记录素数个数
void init(){
isPrime[0]=isPrime[1]=0;//标记0 1不是素数
for(int i=2;i<=N;i++){
if(isPrime[i]){//如果i是素数,存进去
primes[cnt++]=i;
}
for(int j=0;j
积性函数
积性函数：形如
g
c
d
(
a
,
b
)
=
1
gcd(a,b)=1
gcd(a,b)=1且满足
f
(
a
b
)
=
f
(
a
)
f
(
b
)
f(ab)=f(a)f(b)
f(ab)=f(a)f(b)的函数称为积性函数
完全积性函数：对于任意正整数
a
,
b
a,b
a,b都有
f
(
a
b
)
=
f
(
a
)
f
(
b
)
f(ab)=f(a)f(b)
f(ab)=f(a)f(b)
性质
- 两积性函数乘积是积性函数，即若
f
(
x
)
,
g
(
x
)
f(x),g(x)
f(x),g(x)是积性函数，则
h
(
x
)
=
f
(
x
)
g
(
x
)
h(x)=f(x)g(x)
h(x)=f(x)g(x)也是积性函数
- 任何积性函数都能应用线筛法在
O
(
n
)
O(n)
O(n)内求出
1
∼
n
1sim n
1∼n项
二分快速幂与二分龟速乘
二分快速幂
二分幂
- 二分幂，就是平常所用的幂运算化简方法，一般采用递归实现，不建议使用
如
a
b
{
a
∗
(
a
2
)
b
2
,
b
为奇数
(
a
2
)
b
2
,
b
为偶数
a^bleft{ begin{array}{l} a*left( a^2 right) ^{frac{b}{2}},btext{为奇数}\ left( a^2 right) ^{frac{b}{2}},btext{为偶数}\ end{array} right.
ab{a∗(a2)2b,b为奇数(a2)2b,b为偶数
转化为递归方程为
f
(
a
,
b
)
{
1
,
b
=
0
a
∗
f
(
a
2
,
b
2
)
,
b
为奇数
f
(
a
2
,
b
2
)
,
b
为偶数
fleft( a,b right) left{ begin{array}{l} 1,b=0\ a*fleft( a^2,frac{b}{2} right) ,btext{为奇数}\ fleft( a^2,frac{b}{2} right) ,btext{为偶数}\ end{array} right.
f(a,b)⎩⎨⎧1,b=0a∗f(a2,2b),b为奇数f(a2,2b),b为偶数
算法模板
typedef long long ll;
ll efm(ll a,ll b,ll n){
if(b==0) return 1;
if(b&1) return a*efm(a*a%n,b>>1,n);
else return efm(a*a%n,b>>1,n);
}
快速幂
- 采用二分的思想利用二进制快速求解
a
b
a^b
ab。
算法思想
这里用b表示二进制数，
如
3
13
=
3
b
1101
=
3
1
∗
b
1000
∗
3
1
∗
b
100
∗
3
0
∗
b
10
∗
3
1
∗
b
1
3^{13}=3^{b1101}=3^{1*b1000}*3^{1*b100}*3^{0*b10}*3^{1*b1}
313=3b1101=31∗b1000∗31∗b100∗30∗b10∗31∗b1
3
b
10
=
(
3
b
1
)
2
3^{b10}=(3^{b1})^2
3b10=(3b1)2
3
b
100
=
(
3
b
10
)
2
3^{b100}=(3^{b10})^2
3b100=(3b10)2
3
b
1000
=
(
3
b
100
)
2
3^{b1000}=(3^{b100})^2
3b1000=(3b100)2
可以看出，每一项都是前一项的平方，原本需要计算13次的算法被优化到了计算4次，本算法时间复杂度是
O
(
l
o
g
2
b
)
O(log_2b)
O(log2b)。
算法模板
- 通常，本算法的幂非常大，所求结果常需要取模
typedef long long ll;
ll ksm(ll a,ll b,ll n){//a^b%n
ll ret=1;//累乘结果计算
while(b>0){//非0次幂则计算
if(b&1){//判断最低为是否为1，0不需要乘入
ret=ret*a%n;
}
a=a*a%n;//由上述推导可得平方关系
b>>=1;//b右移一位
}
return ret;
}
二分龟速乘
- 对于快速幂算法的改进
二分快速幂算法存在的问题
在使用二分快速幂计算乘法时，尽管采用了%n来防止溢出，但仍然会有溢出现象，因为x*y%n，在x*x时就有可能溢出。
二分乘
- 其实就是龟速乘的二分版本，一般用递归实现，不建议使用
乘法可以写成累加的形式，诸如
3
∗
5
=
3
+
3
∗
4
=
3
+
(
2
∗
3
)
∗
2
=
3
+
6
∗
2
=
3
+
12
3*5=3+3*4=3+(2*3)*2=3+6*2=3+12
3∗5=3+3∗4=3+(2∗3)∗2=3+6∗2=3+12
转化为递归方程为
f
(
a
,
b
)
{
0
,
b
=
0
a
+
f
(
2
a
,
b
2
)
,
b
为奇数
f
(
2
a
,
b
2
)
,
b
为偶数
fleft( a,b right) left{ begin{array}{l} 0,b=0\ a+fleft( 2a,frac{b}{2} right) ,btext{为奇数}\ fleft( 2a,frac{b}{2} right) ,btext{为偶数}\ end{array} right.
f(a,b)⎩⎨⎧0,b=0a+f(2a,2b),b为奇数f(2a,2b),b为偶数
算法模板
typedef long long ll;
ll gsc(ll a,ll b,ll n){
if(b==0) return 0;
if(b&1) return (a+gsc((a<<1)%n,b>>1))%n;
else return gsc((a<<1)%n,b>>1)%n;
}
龟速乘
我们可以让x*y也变成类似于快速幂的运算形式，诸如
3
∗
5
=
3
∗
b
101
=
3
∗
(
1
∗
b
1
+
0
∗
b
10
+
1
∗
b
100
)
3*5=3*b101=3*(1*b1+0*b10+1*b100)
3∗5=3∗b101=3∗(1∗b1+0∗b10+1∗b100)
=
1
∗
3
∗
b
1
+
0
∗
3
∗
b
10
+
1
∗
3
∗
b
100
=1*3*b1+0*3*b10+1*3*b100
=1∗3∗b1+0∗3∗b10+1∗3∗b100
其中
3
∗
b
10
=
3
∗
b
1
+
3
∗
b
1
3*b10=3*b1+3*b1
3∗b10=3∗b1+3∗b1
3
∗
b
100
=
3
∗
b
10
+
3
∗
b
10
3*b100=3*b10+3*b10
3∗b100=3∗b10+3∗b10
不难发现，每一项都是前一项的二倍，由于本算法甚至慢于for循环相加，故得名龟速乘，时间复杂度为
O
(
l
o
g
2
b
)
O(log_2b)
O(log2b)
算法模板
typedef long long ll;
ll gsc(ll a,ll b,ll n){
ll ret=0;//累加结果计算
while(b>0){//非0乘则计算
if(b&1){//判断最低为是否为1，0不需要加入
ret=(ret+a)%n;
}
a=(a+a)%n;//由上述推导可得平方关系
b>>=1;//b右移一位
}
return ret;
}
快速幂的改进
- 引入了龟速乘后，我们便可以改进快速幂算法
typedef long long ll;
ll ksm(ll a,ll b,ll n){
ll ret=1;
while(b>0){
if(b&1){
ret=gsc(ret,a,n);//修改位
}
a=gsc(a,a,n);//修改位
b>>=1;
}
return ret;
}
重要定理
费马小定理
-
b
b
b是质数且
g
c
d
(
a
,
b
)
=
1
→
a
(
p
−
1
)
≡
1
(
m
o
d
n
)
,
a
p
≡
a
(
m
o
d
n
)
gcd(a,b)=1rightarrow a^{(p-1)}equiv1(mod n),a^{p}equiv a(mod n)
gcd(a,b)=1→a(p−1)≡1(mod n),ap≡a(mod n)
欧拉定理
欧拉函数
- 欧拉函数表示
1
,
2
,
3
,
.
.
.
,
n
1,2,3,...,n
1,2,3,...,n中与
n
n
n互质的元素个数,用
φ
(
n
)
varphi(n)
φ(n)表示
-
φ
(
n
)
=
n
(
1
−
1
p
1
)
(
1
−
1
p
2
)
.
.
.
(
1
−
1
p
k
)
=
n
(
p
1
−
1
p
1
)
(
p
2
−
1
p
2
)
.
.
.
(
p
k
−
1
p
k
)
varphi(n)=n(1-frac{1}{p_1})(1-frac{1}{p_2})...(1-frac{1}{p_k})=n(frac{p_1-1}{p_1})(frac{p_2-1}{p_2})...(frac{p_k-1}{p_k})
φ(n)=n(1−p11)(1−p21)...(1−pk1)=n(p1p1−1)(p2p2−1)...(pkpk−1),其中
p
i
p_i
pi表示
n
n
n的第
i
i
i个质因数
欧拉定理
-
∀
a
,
b
∈
N
+
,
g
c
d
(
a
,
n
)
=
1
→
a
φ
(
n
)
≡
1
(
m
o
d
n
)
forall a,b in{N^+},gcd(a,n)=1rightarrow a^{varphi(n)}equiv1(mod n)
∀a,b∈N+,gcd(a,n)=1→aφ(n)≡1(mod n)
欧拉函数算法
- 函数法
int phi(int n){
int ans=n;//公式的乘数n
for(int i=2;i*i<=x;i++){//只能要质因数,循环里面会筛出
if(x%i==0){
ans-=ans/i;//n*(1-1/pi)=n-n/pi
while(n%i==0) n/=i;//筛除n所有的因数i
}
}
if(n>1)//还有剩余，说明剩余数本身也是质因数
ans-=ans/n;
return ans;
}
- 欧拉筛法
欧拉筛法原理见素数-欧拉筛法章节，利用欧拉筛法打表欧拉函数。
int phi[N+1];//存欧拉函数
void init(){
for(int i=1;i<=N;i++) phi[i]=i;
for(int i=2;i<=N;i++){
if(phi[i]==i){//欧拉值是自己则为素数
for(int j=i;j<=N;j+=i){
phi[j]-=phi[j]/i;
}
}
}
}
扩展欧拉定理
a
b
=
{
a
b
m
o
d
φ
(
m
)
,
g
c
d
(
a
,
m
)
=
1
a
b
,
g
c
d
(
a
,
m
)
≠
1
,
b
<
φ
(
m
)
a
(
b
m
o
d
φ
(
m
)
+
φ
(
m
)
)
,
g
c
d
(
a
,
m
)
≠
1
,
b
≥
φ
(
m
)
a^b=left{ begin{array}{l} a^{b mod varphi left( m right) ,gcdleft( a,m right) =1}\ a^b,gcdleft( a,m right) ne 1,b
威尔逊定理
-
当
且
仅
当
p
是
素
数
时
,
(
p
−
1
)
!
≡
−
1
(
m
o
d
n
)
当且仅当p是素数时,(p-1)!equiv-1(mod n)
当且仅当p是素数时,(p−1)!≡−1(mod n)
欧几里得算法(辗转反除法)
- 适用于求最大公因数
- 基本算法
设有两个整数
a
,
b
a,b
a,b的最大公约数为
g
c
d
(
a
,
b
)
gcd(a,b)
gcd(a,b)
设
a
=
q
∗
b
+
r
a=q*b+r
a=q∗b+r,其中
a
,
b
,
q
,
r
a,b,q,r
a,b,q,r均为整数
则
g
c
d
(
a
,
b
)
=
g
c
d
(
b
,
r
)
gcd(a,b)=gcd(b,r)
gcd(a,b)=gcd(b,r),即
g
c
d
(
a
,
b
)
=
g
c
d
(
b
,
a
%
b
)
gcd(a,b)=gcd(b,a%b)
gcd(a,b)=gcd(b,a%b)
- 证明
a
=
q
∗
b
+
r
a=q*b+r
a=q∗b+r
如果
r
=
0
r=0
r=0,则a是b的倍数,b是a,b的最大公约数
如果
r
≠
0
rne0
r=0,任何整除a,b的数必定整数
a
−
q
∗
b
=
r
a-q*b=r
a−q∗b=r,而且任何同时整除b,r的数必定整除
q
∗
b
+
r
=
a
q*b+r=a
q∗b+r=a,所以a,b的公约数集合与b,r的公约数集合是相同的。
int gcd(int a,int b){//最大公约数
return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b){//最小公倍数
return a/gcd(a,b)*b;//防溢出
}
扩展欧几里得
裴蜀定理
- 对于任何整数a,b和他们的最大公因数d,关于未知数x,y的方程
a
x
+
b
y
=
m
ax+by=m
ax+by=m有整数解当且仅当m是d的倍数,即
a
x
+
b
y
=
k
∗
g
c
d
(
a
,
b
)
ax+by=k*gcd(a,b)
ax+by=k∗gcd(a,b)
- 例如,12和42的最大公因数是6,则方程12x+42y=6有整数解
(
−
3
∗
12
+
1
∗
42
=
6
,
4
∗
12
−
1
∗
42
=
6
)
(-3*12+1*42=6,4*12-1*42=6)
(−3∗12+1∗42=6,4∗12−1∗42=6)
- 特别地,方程
a
x
+
b
y
=
1
ax+by=1
ax+by=1有整数解当且仅当整数a,b互质,因此
a
x
+
b
y
=
1
ax+by=1
ax+by=1可以判断a,b互质
- d是最小可以写成
a
x
+
b
y
ax+by
ax+by形式的正整数
扩展欧几里得算法
推导
a
%
b
=
a
−
a
/
b
∗
b
a%b=a-a/b*b
a%b=a−a/b∗b
a
x
+
b
y
=
g
c
d
(
a
,
b
)
=
g
c
d
(
b
,
a
%
b
)
=
b
x
′
+
(
a
%
b
)
y
′
=
b
x
′
+
(
a
−
a
/
b
∗
b
)
y
′
ax+by=gcd(a,b)=gcd(b,a%b)=bx'+(a%b)y'=bx'+(a-a/b*b)y'
ax+by=gcd(a,b)=gcd(b,a%b)=bx′+(a%b)y′=bx′+(a−a/b∗b)y′
移项可得
a
x
+
b
y
=
a
y
′
+
b
(
x
′
−
(
a
/
b
)
y
′
)
ax+by=ay'+b(x'-(a/b)y')
ax+by=ay′+b(x′−(a/b)y′)
有
x
=
y
′
x=y'
x=y′,
y
=
x
′
−
(
a
/
b
)
y
′
y=x'-(a/b)y'
y=x′−(a/b)y′
通解
求
a
x
+
b
y
=
c
ax+by=c
ax+by=c
设特解为
x
0
,
y
0
x_0,y_0
x0,y0
通解为
x
=
x
0
+
k
∗
(
b
/
g
c
d
(
a
,
b
)
)
,
y
=
q
−
k
∗
(
a
/
g
c
d
(
a
,
b
)
)
x=x_0+k*(b/gcd(a,b)),y=q-k*(a/gcd(a,b))
x=x0+k∗(b/gcd(a,b)),y=q−k∗(a/gcd(a,b)),
k
k
k为任意整数
对于一般形式
a
x
+
b
y
=
c
ax+by=c
ax+by=c的特解或通解为
a
′
x
′
+
b
′
y
′
=
g
c
d
(
a
,
b
)
a'x'+b'y'=gcd(a,b)
a′x′+b′y′=gcd(a,b)的特解或通解乘以系数
c
/
g
c
d
(
a
,
b
)
c/gcd(a,b)
c/gcd(a,b)
令
t
=
b
/
d
t=b/d
t=b/d，
x
x
x的最小整数解为
(
x
%
t
+
t
)
%
t
(x%t+t)%t
(x%t+t)%t
int exgcd(int a,int b,int c,int &x,int &y){
if(b==0){//最终情况ax=c,x=c/a
x=c/a;
y=0;
return a;
}
int r=exgcd(b,a%b,x,y);
int t=x;
x=y;//x=y
y=t-a/b*y;//y=x%y
return r;
}
举例
gcd(28,10)=gcd(10,8)=gcd(8,2)=gcd(2,0)=2
gcd(2,0):x=1,y=0,2x+0y=2
gcd(8,2):x=0,y=1-0=1,8x+2y=2
gcd(10,8):x=1,y=0-1*1=-1,10x+8y=2
gcd(28,10):x=-1,y=-1-2*(-1)=3,28x+10y=2
线性同余方程
定义
- 形如
a
x
≡
b
(
m
o
d
n
)
axequiv b(mod n)
ax≡b(mod n)的方程
性质
- 此方程对于未知数
x
x
x有解当且仅当
g
c
d
(
a
,
n
)
∣
b
gcd(a,n)|b
gcd(a,n)∣b
-
d
=
g
c
d
(
a
,
n
)
d=gcd(a,n)
d=gcd(a,n),若
d
∣
b
d|b
d∣b,则方程恰好有
d
d
d个模
n
n
n不同余的解,否则方程无解
- 若
x
0
x_0
x0是方程的任一解,则该方程对模
n
n
n有
d
d
d个不同的解,分别为
x
i
=
x
0
+
k
∗
(
b
/
d
)
,
(
k
=
0
,
1
,
2
,
.
.
.
,
d
−
1
)
x_i=x_0+k*(b/d),(k=0,1,2,...,d-1)
xi=x0+k∗(b/d),(k=0,1,2,...,d−1)
解线性同余方程
a
x
≡
b
(
m
o
d
n
)
→
a
x
+
n
y
=
b
,
d
=
g
c
d
(
a
,
n
)
axequiv b(mod n)rightarrow ax+ny=b,d=gcd(a,n)
ax≡b(mod n)→ax+ny=b,d=gcd(a,n),若不满足
d
∣
b
d|b
d∣b,则方程无解,否则
a
x
0
+
n
y
0
=
d
ax_0+ny_0=d
ax0+ny0=d,利用扩展欧几里得求得一组特解
(
x
0
,
y
0
)
(x_0,y_0)
(x0,y0)后,
x
=
x
0
∗
b
/
d
%
n
x=x_0*b/d%n
x=x0∗b/d%n就是原方程的一个解,且有
d
d
d个不同解,为
x
i
=
(
x
0
+
k
∗
b
/
d
)
%
n
,
0
≤
k
<
d
x_i=(x_0+k*b/d)%n,0le k
最小整数解
- 由于一元线性同余方程的通解可以写成
r
e
s
=
(
X
+
i
∗
b
/
d
)
(
m
o
d
n
)
=
X
+
i
∗
b
/
d
+
n
∗
y
res=(X+i*b/d)(mod n)=X+i*b/d+n*y
res=(X+i∗b/d)(mod n)=X+i∗b/d+n∗y,由于
y
y
y与
i
i
i均为变量因此可以将其合并得到式子
r
e
s
=
X
+
y
∗
n
/
d
res=X+y*n/d
res=X+y∗n/d(其中
i
=
0
i=0
i=0,将原式
n
∗
y
n*y
n∗y看作
d
∗
y
∗
n
/
d
d*y*n/d
d∗y∗n/d,将
d
∗
y
d*y
d∗y看作
y
y
y),因此可以得到
r
e
s
=
X
(
m
o
d
n
/
d
)
res=X(mod n/d)
res=X(mod n/d),设
n
/
d
=
t
n/d=t
n/d=t,其最小整数解可以表示为
(
X
%
t
+
t
)
%
t
(X%t+t)%t
(X%t+t)%t
void LCT(int a,int b,int n){
int X,Y,d;
long long res;
long long min_res;
d=gcd(a,n);
exgcd(a,n,X,Y);
if(b%d == 0){
X=X*(b/d)%n;//得到同于方程一解
for(int i=0;i
中国剩余定理
定义
对于模线性方程组
x
≡
a
1
(
m
o
d
m
1
)
xequiv a_1(mod m_1)
x≡a1(mod m1)
x
≡
a
2
(
m
o
d
m
2
)
xequiv a_2(mod m_2)
x≡a2(mod m2)
.
.
.
...
...
x
≡
a
n
(
m
o
d
m
n
)
xequiv a_n(mod m_n)
x≡an(mod mn)
假设整数
m
1
,
m
2
,
.
.
.
,
m
n
m_1,m_2,...,m_n
m1,m2,...,mn两两互质，则方程组有解，通解可以构造如下:
设
M
=
m
1
∗
m
2
∗
.
.
.
∗
m
n
=
∏
m
i
M=m_1*m_2*...*m_n=prod{m_i}
M=m1∗m2∗...∗mn=∏mi，并设
M
i
=
M
m
i
,
t
i
=
M
i
−
1
M_i=frac{M}{m_i},t_i=M_i^{-1}
Mi=miM,ti=Mi−1，表示
M
i
M_i
Mi在模
m
i
m_i
mi意义下的乘法逆元，即
M
i
t
i
=
1
(
m
o
d
m
i
)
M_it_i=1(mod m_i)
Miti=1(mod mi)
方程通解:
x
=
a
1
t
1
M
1
+
a
2
t
2
M
2
+
.
.
.
+
a
n
t
n
M
n
=
∑
i
=
1
n
a
i
t
i
M
i
+
k
M
,
k
∈
N
x=a_1t_1M_1+a_2t_2M_2+...+a_nt_nM_n=sum_{i=1}^{n}a_it_iM_i+kM, kin N
x=a1t1M1+a2t2M2+...+antnMn=∑i=1naitiMi+kM, k∈N
常规中国剩余定理(各m互质)
- 计算所有模的累积
M
=
m
1
∗
m
2
∗
⋯
∗
m
n
M=m_1*m_2*dots *m_n
M=m1∗m2∗⋯∗mn
- 计算第
i
i
i个方程
- 计算
M
i
=
M
m
i
M_i=frac{M}{m_i}
Mi=miM
- 计算
M
i
M_i
Mi在模
m
i
m_i
mi下的乘法逆元
t
i
=
M
i
−
1
(
m
o
d
m
i
)
t_i=M_i^{-1}(mod m_i)
ti=Mi−1(mod mi)
- 方程的最小正整数解为
x
=
∑
i
=
1
n
a
i
∗
t
i
∗
M
i
(
m
o
d
M
)
x=sum_{i=1}^{n}{a_i*t_i*M_i}(mod M)
x=∑i=1nai∗ti∗Mi(mod M)，通解为
x
=
∑
i
=
1
n
a
i
∗
t
i
∗
M
i
+
k
M
,
k
∈
N
x=sum_{i=1}^{n}{a_i*t_i*M_i}+kM, kin N
x=∑i=1nai∗ti∗Mi+kM, k∈N
int CRT(int a[],int m[],int n) {
int M=1,ans=0;
for(int i=1;i<=n;i++){
M*=m[i];//求m1*m2*...*mn
}
for(int i=1;i<=n;i++){
int x,y;
int Mi=M/m[i];//Mi
exgcd(Mi,m[i],x,y);//求Mi在mi下的的乘法逆元x
ans=(ans+a[i]*x*Mi%M)%M;//结果加上ai*ti*Mi
}
return (ans%M+M)%M;//模M下的最小正整数解
}
扩展中国剩余定理(m不互质)
两个方程
设两个方程分别是
x
=
n
1
(
m
o
d
m
1
)
x=n_1(mod m_1)
x=n1(mod m1)、
x
=
n
1
(
m
o
d
m
2
)
x=n_1(mod m_2)
x=n1(mod m2)；
将它们转化为不定方程
x
=
m
1
p
+
n
1
=
m
2
q
+
n
2
x=m_1p+n_1=m_2q+n_2
x=m1p+n1=m2q+n2，其中
p
,
q
p,q
p,q整数，则有
m
1
p
−
m
2
q
=
a
2
−
a
1
m_1p-m_2q=a_2-a_1
m1p−m2q=a2−a1。
由裴蜀定理，当
a
2
−
a
1
a_2-a_1
a2−a1不能被
g
c
d
(
m
1
,
m
2
)
gcd(m_1,m_2)
gcd(m1,m2)整除时，无解；
其他情况下，可以通过扩展欧几里得算法解出来一组可行解
(
p
,
q
)
(p,q)
(p,q)；
则原来的两方程组成的模方程组的解为
x
=
b
(
m
o
d
M
)
x=b(mod M)
x=b(mod M)，其中
b
=
m
q
p
+
a
1
,
M
=
l
c
m
(
m
1
,
m
2
)
b=m_qp+a_1,M=lcm(m_1,m_2)
b=mqp+a1,M=lcm(m1,m2)。
多个方程
用上面的方法两两合并即可。
乘法逆元
扩展欧几里得法
利用
a
∗
x
=
1
(
m
o
d
b
)
a*x=1(mod b)
a∗x=1(mod b)，则
x
x
x是
a
a
a在
m
o
d
b
mod b
mod b下的乘法逆元
费马小定理
若
p
p
p为素数，
a
a
a为正整数，且
g
c
d
(
a
,
b
)
=
1
gcd(a,b)=1
gcd(a,b)=1，则有
a
p
−
1
=
1
(
m
o
d
p
)
a^{p-1}=1(mod p)
ap−1=1(mod p)，显然
a
−
1
=
a
p
−
2
(
m
o
d
p
)
a^{-1}=a^{p-2}(mod p)
a−1=ap−2(mod p)
费马小定理要用快速幂实现
线性筛法
用于求一连串数字对于一个
m
o
d
p
mod p
mod p的乘法逆元
1
−
1
=
1
(
m
o
d
p
)
1^{-1}=1(mod p)
1−1=1(mod p)
设
p
=
k
∗
i
+
r
(
1
<
r
<
i
<
p
)
p=k*i+r(1
乘以
i
−
1
,
r
−
1
i^{-1},r^{-1}
i−1,r−1，
k
∗
r
−
1
+
i
−
1
=
0
(
m
o
d
p
)
k*r^{-1}+i^{-1}=0(mod p)
k∗r−1+i−1=0(mod p)
i
−
1
=
−
k
∗
r
−
1
=
−
(
p
/
i
)
∗
(
p
%
i
)
−
1
i^{-1}=-k*r^{-1}=-(p/i)*(p%i)^{-1}
i−1=−k∗r−1=−(p/i)∗(p%i)−1
于是我们就得到了
1
∼
n
1sim n
1∼n关于
(
m
o
d
p
)
(mod p)
(mod p)的乘法逆元
二次剩余
x
2
=
n
(
m
o
d
p
)
x^2=n(mod p)
x2=n(mod p)，其中
n
n
n是常数，
p
p
p是奇素数
常见用途
由
x
2
=
n
(
m
o
d
p
)
x^2=n(mod p)
x2=n(mod p)得出
x
=
n
(
m
o
d
p
)
x=sqrt{n}(mod p)
x=n
(mod p)
解的数量
对于
x
2
=
n
(
m
o
d
p
)
x^2=n(mod p)
x2=n(mod p)，能满足“
n
n
n是模
p
p
p的二次剩余”的 一共有
p
−
1
2
frac{p-1}{2}
2p−1个（
0
0
0不包括在内），非二次剩余有
p
−
1
2
frac{p-1}{2}
2p−1个。
勒让德符号
n
p
=
{
1
,
p
∤
n
且
n
是
p
的二次剩余
−
1
,
p
∤
n
不是
p
的二次剩余
0
,
p
∣
n
frac{n}{p}=left{ begin{array}{l} 1,pnmid ntext{且}ntext{是}ptext{的二次剩余}\ -1,pnmid ntext{不是}ptext{的二次剩余}\ 0,pmid n\ end{array} right.
pn=⎩⎨⎧1,p∤n且n是p的二次剩余−1,p∤n不是p的二次剩余0,p∣n
勒让德符号可以判断一个数
n
n
n是否为二次剩余，具体判断
n
n
n是否为
p
p
p的二次剩余，需要通过欧拉判别准则来实现。
欧拉判别准则
n
p
=
n
p
−
1
2
(
m
o
d
p
)
frac{n}{p}=n^{frac{p-1}{2}}left( mod p right)
pn=n2p−1(mod p)
若
p
p
p是二次剩余，当且仅当
n
p
=
1
(
m
o
d
p
)
frac{n}{p}=1(mod p)
pn=1(mod p)。
若
p
p
p是非二次剩余，当且仅当
n
p
=
−
1
(
m
o
d
p
)
frac{n}{p} =-1(mod p)
pn=−1(mod p)。
Cipolla算法
找到一个数
n
n
n满足
a
2
−
n
a^2-n
a2−n是非二次剩余，这里通过生成随机数再检验的方法来实现，由于非二次剩余的数量为
p
−
1
2
frac{p-1}{2}
2p−1，接近
p
2
frac{p}{2}
2p，所以期望约
2
2
2次就可以找到这个数。
建立一个“复数域”，并不是实际意义上的复数域，而是根据复数域的概念建立的一个类似的域。 在复数中
i
2
=
−
1
i^2=-1
i2=−1，这里定义
i
2
=
a
2
−
n
i^2=a^2-n
i2=a2−n，于是就可以将所有的数表达为
A
+
B
i
A+Bi
A+Bi的形式，这里的
A
A
A和
B
B
B都是模意义下的数，类似复数中的实部和虚部。
在有了
i
i
i和
a
a
a后可以直接得到答案，
x
2
=
n
(
m
o
d
p
)
x^2=n(mod p)
x2=n(mod p)的解为
x
=
(
a
+
i
)
p
+
1
2
x=(a+i)^{frac{p+1}{2}}
x=(a+i)2p+1。
证明
-
(
a
+
b
)
p
=
a
p
+
b
p
(
m
o
d
p
)
(a+b)^p=a^p+b^p(mod p)
(a+b)p=ap+bp(mod p)
(
a
+
b
)
p
=
∑
i
=
0
p
C
p
i
a
p
−
i
b
i
=
∑
i
=
0
p
p
!
p
−
i
!
i
!
a
p
−
i
b
i
=
a
p
+
b
p
(
m
o
d
p
)
(a+b)^p=sum_{i=0}^{p}C_p^ia^{p-i}b^i=sum_{i=0}^{p}frac{p!}{{p-i}!i!}a^{p-i}b^i=a^p+b^p(mod p)
(a+b)p=i=0∑pCpiap−ibi=i=0∑pp−i!i!p!ap−ibi=ap+bp(mod p)
-
i
p
=
−
i
(
m
o
d
p
)
i^p=-i(mod p)
ip=−i(mod p)
i
p
=
i
p
−
1
i
=
(
i
2
)
p
−
1
2
i
=
(
a
2
−
n
)
p
−
1
2
i
=
−
i
(
m
o
d
p
)
i^p=i^{p-1}i=(i^2)^{frac{p-1}{2}}i=(a^2-n)^{frac{p-1}{2}}i=-i(mod p)
ip=ip−1i=(i2)2p−1i=(a2−n)2p−1i=−i(mod p)
-
a
p
=
a
(
m
o
d
p
)
a^p=a(mod p)
ap=a(mod p)是费马小定理
x
=
(
a
+
i
)
p
+
1
2
x=(a+i)^frac{p+1}{2}
x=(a+i)2p+1
=
(
(
a
+
i
)
p
+
1
)
1
2
=((a+i)^{p+1})^frac{1}{2}
=((a+i)p+1)21
=
(
(
a
+
i
)
p
(
a
+
i
)
)
1
2
=((a+i)^p(a+i))^frac{1}{2}
=((a+i)p(a+i))21
=
(
(
a
p
+
i
p
)
(
a
+
i
)
)
1
2
=((a^p+i^p)(a+i))^frac{1}{2}
=((ap+ip)(a+i))21
=
(
(
a
−
i
)
(
a
+
i
)
)
1
2
=((a-i)(a+i))^frac{1}{2}
=((a−i)(a+i))21
=
(
a
2
−
i
2
)
1
2
=(a^2-i^2)^frac{1}{2}
=(a2−i2)21
=
(
a
2
−
(
a
2
−
n
)
)
1
2
=(a^2-(a^2-n))^frac{1}{2}
=(a2−(a2−n))21
=
n
1
2
(
m
o
d
p
)
=n^frac{1}{2}(mod p)
=n21(mod p)
#include
using namespace std;
typedef long long ll;
int t;
ll n,p;
ll w;
struct num{//建立一个复数域
ll x,y;
};
num mul(num a,num b,ll p){//复数乘法
num ans={0,0};
ans.x=((a.x*b.x%p+a.y*b.y%p*w%p)%p+p)%p;
ans.y=((a.x*b.y%p+a.y*b.x%p)%p+p)%p;
return ans;
}
ll binpow_real(ll a,ll b,ll p){//实部快速幂
ll ans=1;
while (b) {
if (b & 1) ans=ans*a%p;
a=a*a%p;
b >>=1;
}
return ans%p;
}
ll binpow_imag(num a,ll b,ll p){//虚部快速幂
num ans={1,0};
while (b) {
if (b & 1) ans=mul(ans,a,p);
a=mul(a,a,p);
b >>=1;
}
return ans.x%p;
}
ll cipolla(ll n,ll p){
n%=p;
if(p==2) return n;
if(binpow_real(n,(p-1)/2,p)==p-1) return -1;
ll a;
while(1){//生成随机数再检验找到满足非二次剩余的a*a-n
a=rand()%p;
w=((a*a%p-n)%p+p)%p;
if(binpow_real(w,(p-1)/2,p)==p-1) break;//模里面p-1就是-1,欧拉判别准则
}
num x={a,1};//x=a+1*i
return binpow_imag(x,(p+1)/2,p);
}
唯一分解定理
唯一分解定理又称为算数基本定理，基本内容是：
每个大于
1
1
1的自然数，要么本身就是质数，要么可以写为
2
2
2个或以上的质数的积，而且这些素因子按大小排列之后，写法仅有一种方式，即
N
=
p
1
a
1
∗
p
2
a
2
∗
⋯
∗
p
n
a
n
N=p_1^{a_1}*p_2^{a_2}*dots*p_n^{a_n}
N=p1a1∗p2a2∗⋯∗pnan，其中
p
i
(
p
i
>
1
)
p_i(p_i>1)
pi(pi>1)是素数。
设
F
(
N
)
F(N)
F(N)代表
N
N
N的正因子数量，则
F
(
N
)
=
(
1
+
a
1
)
(
1
+
a
2
)
…
(
1
+
a
n
)
F(N)=(1+a_1)(1+a_2)dots(1+a_n)
F(N)=(1+a1)(1+a2)…(1+an)
设
G
(
N
)
G(N)
G(N)表示
N
N
N的正因子积，则
G
(
N
)
=
(
1
+
p
1
1
+
⋯
+
p
1
a
1
)
(
1
+
p
2
1
+
⋯
+
p
2
a
2
)
…
(
1
+
p
n
1
+
⋯
+
p
n
a
n
)
G(N)=(1+p_1^1+dots+p_1^{a_1})(1+p_2^1+dots+p_2^{a_2})dots(1+p_n^1+dots+p_n^{a_n})
G(N)=(1+p11+⋯+p1a1)(1+p21+⋯+p2a2)…(1+pn1+⋯+pnan)
莫比乌斯
- 待更新
逆序数
- 待更新
原根
- 待更新
离散对数
- 待更新
版权声明
- 本文档归cout0所有，仅供学习使用，未经允许，不得转载。
