数学基础

此部分由我队友完成。浏览体验可能会有所不同因为水平比我强


有些地方无法正常浏览,可能是因为我队友有些用的LateX语法,markdown渲染不出来

组合数

1. 求组合数

根据不同的数据范围,求组合数也可以运用不同的方法。总的式子:

Cab=a!b!(ab)!C_a^b=\frac{a!}{b!(a-b)!}

表示从aa个物品中选出bb个的方案数。

(1) 递推法

使用递推式Cab=Ca1b+Ca1b1C_a^b=C_{a-1}^b+C_{a-1}^{b-1}

证明:考虑已经得知了Ca1k,k[0,b]C_{a-1}^k,k\in[0,b]的结果,那么当前有aa个物品时,第aa个物品要么被选,要么不被选中。若被选中,则方案一共有Ca1b1C_{a-1}^{b-1}个,若不被选中,则方案有Ca1bC_{a-1}^b个,方案累加,得证。

时间复杂度O(n2)O(n^2)

1
2
3
4
5
6
7
8
9
10
void init(){
for (int i=0;i<N;++i){
for (int j=0;j<=i;++j){
if (!j) C[i][j] = 1;
else{
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % M;
}
}
}
}
(2) 通过预处理逆元的方式求组合数

直接求出a!,1b!,1(ab)!a!,\frac{1}{b!},\frac{1}{(a-b)!},然后再相乘。

时间复杂度O(nlogn)O(n\log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int n;
const int N = 1e5 + 5;
const ll M = 1e9 + 7;
ll fac[N], invf[N];// 阶乘 阶乘的逆元

void init(){
fac[0] = invf[0] = 1LL;
for (int i=1;i<N;++i){
fac[i] = fac[i-1] * i % M;
invf[i] = invf[i-1] * qmi(i, M-2, M) % M;
}
}

int main(void){
scanf("%d", &n);
init();
ll a, b;
for (int i=1;i<=n;++i){
scanf("%lld%lld", &a, &b);
ll ans = fac[a] * invf[b] % M * invf[a - b] % M;
printf("%lld\n", ans);
}

return 0;
}
(3) 分解质因数法求组合数(高精度)

首先,可以把a!a!写成a!=p1a1×p2a2×...×pkaka!=p_1^{a_1}\times p_2^{a_2}\times ...\times p_k^{a_k}的形式,那么CabC_a^b的答案肯定可以写成Cab=p1b1×p2b2×...×pkbk,i[1,k],biaiC_a^b=p_1^{b_1}\times p_2^{b_2}\times ...\times p_k^{b_k},\forall i\in[1,k],b_i\leq a_i

因此,设sis_ia!a! 中包含的质因子 pip_i 的个数减去b!,(ab)!b!,(a-b)!中包含的pip_i 的个数,则Cab=i=1kpisiC_a^b=\prod_{i=1}^{k} p_i^{s_i}

那么,a!a!包含的质因子个数为多少呢?答案是ap+ap2+ap3...\lfloor\frac{a}{p}\rfloor+\lfloor\frac{a}{p^2}\rfloor+\lfloor\frac{a}{p^3}\rfloor...

  • 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
const int N = 5000 + 5;
int p[N], sa[N], cnt;
bool st[N];

void Euler(int n){
for (int i=2;i<=n;++i){
if (!st[i]) p[++cnt] = i;
for (int j=1;p[j]<=n/i;++j){
st[p[j] * i] = true;
if (i % p[j] == 0) break;
}
}
}

int get(int n, int p){
int res = 0;
while (n){
res += n/p;
n/=p;
}
return res;
}

vector<int> mul(vector<int>& A, int b){
vector<int> res; int t = 0;
for (int i=0;i<A.size();++i){
t += A[i]*b;
res.push_back(t % 10), t /= 10;
}
while (t){ res.push_back(t%10), t /= 10;}
while (res.back()==0 && res.size()>1) res.pop_back();
return res;
}

int main(void){
int a, b;
scanf("%d%d", &a, &b);
Euler(a);
for (int i=1;i<=cnt;++i){
int cur = p[i];
sa[i] = get(a, cur) - get(a-b, cur) - get(b, cur);
}

vector<int> res;
res.push_back(1);
for (int i=1;i<=cnt;++i){
for (int j=0;j<sa[i];++j){
res = mul(res, p[i]);
}
}

for (int i=res.size()-1;i>=0;--i){
printf("%d", res[i]);
}
puts("");

return 0;
}
(4) Lucas定理求组合数
  • Lucas定理CabCamodpbmodp×Ca/pb/p(modp)C_a^b \equiv C_{a\mod p}^{b \mod p}\times C_{a/p}^{b/p} (\mod p)

  • 代码

其中,组合数直接通过公式Cab=a!b!(ab)!=a×(a1)×...×(ab+1)b!C_a^b=\frac{a!}{b!(a-b)!}=\frac{a\times (a-1)\times...\times (a-b+1)}{b!}求得

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll C(ll a, ll b, ll p){
if (b > a) return 0;
ll res = 1;
for (int i=1, j=a;i<=b;++i, --j){
res = res * j % p; // 分子
res = res * qmi(i, p-2, p) % p; // 分母
}
return res;
}

ll lucas(ll a, ll b, ll p){
if (a<p && b<p) return C(a, b, p);
return C(a%p, b%p, p) * lucas(a/p, b/p, p) % p;
}
(5) 取对数求组合数(可能有浮点误差)

此种方法大概可以计算1000以内的组合数。

先假设mn2m\leq \frac{n}{2}吧,否则因为C(n,m)=C(n,mn)C(n,m)=C(n,m-n),令 m=mnm=m-n

x=lnC(n,m)=ln(n!m!(nm)!)=i=1nlnii=1mlnii=1nmlnix=\ln C(n,m)=\ln (\frac{n!}{m!(n-m)!})=\sum\limits _{i=1}^n\ln i-\sum\limits _{i=1}^m\ln i-\sum\limits _{i=1}^{n-m}\ln i

这样就可以直接计算前缀和lnn\ln n,则C(n,m)=exC(n,m)=e^x

2. 常用公式

(1) 二项式定理

(x+y)^n=\left(\begin{array}{} n\\ 0 \end{array}\right)x^ny^0+\left(\begin{array}{} n\\ 1 \end{array}\right)x^{n-1}y^1+...+\left(\begin{array}{} n\\ n-1 \end{array}\right)x^1y^{n-1}+\left(\begin{array}{} n\\ n \end{array}\right)x^0y^n

也可写成(x+y)^n=\sum\limits_{k=0}^n\left(\begin{array}{} n\\ k \end{array}\right)x^{n-k}y^k=\sum\limits_{k=0}^n\left(\begin{array}{} n\\ k \end{array}\right)x^{k}y^{n-k}

其中,\left(\begin{array}{} n\\ k \end{array}\right)=C_n^k=\frac{n!}{k!(n-k)!}。

二项式定理的一个常用形式为(1+x)n=k=0nCnkxk(1+x)^n=\sum\limits_{k=0}^n C_n^kx^k

那么很明显,(1x)n=k=0n(1)kCnkxk(1-x)^n=\sum\limits_{k=0}^n (-1)^kC_n^kx^k

(2) 其他的一些小公式

Cn0+Cn1+...+Cnn=2nC_n^0+C_n^1+...+C_n^n=2^n(从nn取任意个数,显然二进制取或不取)

Cab=Ca1b+Ca1b1C_a^b=C_{a-1}^b+C_{a-1}^{b-1}(类似DP思想,对于第bb个数,取或不取)

Cm+nn=Cm0Cnn+Cm1Cnn1+...+CmnCn0C_{m+n}^n=C_m^0C_n^n+C_m^1C_n^{n-1}+...+C_m^nC_n^0(从mm个数取nn个,nn个取0个开始遍历)

Cnm=CnnmC_n^m=C_n^{n-m}(显然从nn中取mm个的方案数和从nn中取nmn-m个的方案数是一样的)

(这些递推式还是挺容易证明的就不写了,敲公式好累)

(2) 乘法原理和加法原理:类类独立,步步相关
  1. 加法原理:做一件事情,完成它可以有nn类办法,在第一类办法中有m1m_1种不同的方法,在第二类办法中有m2m_2种不同的方法,……,在第nn类办法中有mnm_n种不同的方法。那么完成这件事共有N=i=1nmiN=\sum_{i=1}^n m_i种不同的方法。

  2. 乘法原理:做一件事情,完成它需要分成n个步骤,做第一步有m1m_1种不同的方法,做第二步有m2种不同的方法,……,做第nn步有种mnm_n不同的方法,那么完成这件事有Ni=1nmiN=\prod_{i=1}^n m_i种不同的方法。

(3) 可重复元素的组合问题

从n个元素中,可重复的挑选m个元素组成集合,求:不同的集合有多少个?

答案:Cn+m1mC_{n+m-1}^m

证明:隔板法。

∣∗∣∗∗∗∗∣∣∗∗∗∣∣∗∣(|是边界,*是球)

假设这里有n个盒子,m个球,如果有k个球被放在了第i个盒子里,那么就相当于第i个数被选了k次。那么去掉两端边界,就相当于摆放n-1个盒子的边界和m个球有多少种摆放方式。从里面选择r个位置放球 剩余的都是盒子边界,因此答案就是Cn+m1mC_{n+m-1}^m

这里有位老哥用dp在O(n2)O(n^2)搞定了,俺觉得也可以一看wwww,部分dp表真是一个好东西啊。

https://blog.csdn.net/m0_37602827/article/details/100624871

3. 常用定理

(1) Lucas定理

结论CabCamodpbmodp×Ca/pb/p(modp)C_a^b \equiv C_{a\mod p}^{b \mod p}\times C_{a/p}^{b/p} (\mod p)pp为素数)

它还可以写成如下形式:

pp为素数,则nnpp进制表示为(ak,ak1,...,a0)(a_k,a_{k-1},...,a_0)mmpp进制表示为(bk,bk1,...,b0)(b_k,b_{k-1},...,b_0)

CnmCakbkCak1bk1...Ca0b0(modp)C_n^m\equiv C_{a_k}^{b_k}·C_{a_{k-1}}^{b_{k-1}}...C_{a_0}^{b_0} (\mod p)

很容易看出来,它就是形式一运用数学归纳法可以得出的结论。

证明

引理1 C(p,x)0(modp),0<x<pC(p,x) \equiv 0(\mod p), 0<x<p

证明:$C(p,x)\equiv \frac{p!}{x!(p-x)!}\equiv \frac{p\times (p-1)!}{x\times(x-1)\times(p-x)!} $

由于pp为素数,所以x(0,p),(p,x)=1\forall x\in(0,p),(p,x)=1,故xCp1x1x|C_{p-1}^{x-1},则p(pxCp1x1)p|(\frac{p}{x}C_{p-1}^{x-1})

所以C(p,x)p×(x1modp)×C(p1,x1)0modpC(p,x) \equiv p\times(x^{-1} \mod p)\times C(p-1,x-1)\equiv 0\mod p

引理2 (1+x)p(1+xp)modp(1+x)^p \equiv (1+x^p) \mod p

根据二项式定理可得(1+x)p=k=0pCpkxk(1+x)^p=\sum\limits _{k=0}^pC_p^kx^k

由引理1可得k=0pCpkxkC(p,0)x0+C(p,p)xp(1+xp)modp\sum\limits _{k=0}^pC_p^kx^k\equiv C(p,0)x^0+C(p,p)x^p\equiv (1+x^p) \mod p

下面正式推导Lucas定理。

假设n=q1p+r1,m=q2p+r2n=q_1p+r_1,m=q_2p+r_2,则q1=n/p,q2=m/pq_1=n/p,q_2=m/p

(1+x)n(1+x)q1p+r1(1+x)q1p×(1+x)r1[(1+x)p]q1×(1+x)r1(1+xp)q1×(1+x)r1i=0q1C(q1,i)xp×i×j=0r1C(r1,j)xj(modp)(1+x)^n\equiv (1+x)^{q_1p+r_1}\equiv (1+x)^{q_1p}\times(1+x)^{r_1}\equiv [(1+x)^p]^{q_1}\times(1+x)^{r_1} \\ (1+x^p)^{q_1}\times(1+x)^{r_1} \equiv \sum\limits _{i=0}^{q_1}C(q_1,i)x^{p\times i}\times \sum\limits _{j=0}^{r_1}C(r_1,j)x^{j} (\mod p)

(1+x)n=i=0nC(n,i)xi(1+x)^n=\sum\limits _{i=0}^{n}C(n,i)x^{i}

i=0nC(n,i)xii=0q1C(q1,i)xp×i×j=0r1C(r1,j)xj(modp)\therefore \sum\limits _{i=0}^{n}C(n,i)x^{i}\equiv \sum\limits _{i=0}^{q_1}C(q_1,i)x^{p\times i}\times \sum\limits _{j=0}^{r_1}C(r_1,j)x^{j} (\mod p)

由二项式定理可知,CnmC_n^m(1+x)n(1+x)^n展开式中xmx^m项前面的系数

m=q2p+r2,q2=m/p,r2=mmp×p\because m=q_2p+r_2,\therefore q_2=m/p,r_2=m-\lfloor \frac{m}{p} \rfloor \times p

C(n,m)xmC(q1,q2)xp×q2×C(r1,r2)xr2(modp)C(n,m)x^{m}\equiv C(q_1,q_2)x^{p\times q_2}\times C(r_1,r_2)x^{r_2} (\mod p)

CnmCq1q2Cr1r2(modp)C_n^m\equiv C_{q_1}^{q_2}·C_{r_1}^{r_2} (\mod p),得证。

推论1 C(n,m)C(n,m)为奇数的充要条件为,在二进制表示下(p=2p=2),i[0,k],aibk\forall i\in[0,k],a_i\geq b_k

证明:首先,C(0,0)=1,C(0,1)=0,C(1,0)=1,C(1,1)=1C(0,0)=1,C(0,1)=0,C(1,0)=1,C(1,1)=1

考虑C(n,m)mod2C(n,m)\mod 2,则对于nn上的为1的位aia_ibib_i能取0或1,对于ai=0a_i=0,则bib_i必须为0,得证。

例题:HDU4349 Xiao Ming’s Hope 结论就是2sum(ai=1)2^{sum(a_i=1)} 这玩意还真会考到啊orz

(2) 扩展Lucas定理

前置知识:卢卡斯定理 中国剩余定理

扩展Lucas定理用于求解以下公式:

CabmodpC_a^b \mod p,其中pp不一定是质数。

由整数的唯一分解定理,对pp进行质因数分解,p=p1a1×p2a2×..×pkakp=p_1^{a_1}\times p_2^{a_2}\times .. \times p_k^{a_k},显然i,j[1,k],ij,(piai,pjaj)=1\forall i,j \in [1,k], i\neq j, (p_i^{a_i},p_j^{a_j})=1

提高篇中已证明

筛法

1. 埃氏筛

  • 主要思想:筛掉所有质数的倍数
  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 为什么j可以从i*i开始?
// 假设i=7, 那么比i小的所有的质数, 已经把2*7,3*7,5*7这样的数筛掉了, 所有可以直接从7*7开始筛
void Eratosthenes(){
for (int i=2;i<=n;++i) st[i] = 1;
for (int i=2;i<=n;++i){
if (st[i]){
p[++cnt] = i;
if ((ll)i*i > n) continue;
for (int j=i*i;j<=n;j+=i){
st[j] = false;
}
}
}
}
  • 时间复杂度分析

    如果是筛所有的数的倍数,那么会筛N2+N3+...+NN=N×(12+13+...+1N)\frac{N}{2}+\frac{N}{3}+...+\frac{N}{N}=N\times(\frac{1}{2}+\frac{1}{3}+...+\frac{1}{N}) 次。

​ 由于调和级数1+12+13+...+1N=ln(N+1)+r1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{N}=ln(N+1)+rrr为欧拉常数,r0.5772156649r\approx 0.5772156649。因此,时间复杂度可近似为O(NlnN)<O(NlogN)O(NlnN)<O(NlogN)

​ 当只筛质数时,由质数分布定理可得NN中约有π(N)=NlnN\pi(N)=\frac{N}{ln N}个质数,因此时间复杂度估算结果为O(NlnNlnN)O(\frac{NlnN}{lnN}),即非常接近O(N)O(N)。在实际计算下,埃氏筛的时间复杂度为O(NloglogN)O(NloglogN)

2. 欧拉筛

  • 主要思想:每个合数只被筛一次的算法。
  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Euler(){
for (int i=2;i<=n;++i){
if (!st[i]) p[++cnt] = i;
for (int j=1;p[j]<=n/i;++j){
st[p[j] * i] = true;
if (i % p[j] == 0) break;
}
}
}
// 为什么每个合数只会被筛一次呢?
// 因为每个合数只会被它的最小质因子筛掉
// 从小到大枚举p[j],当i%p[j]==0时, break。
// 1. 当i%p[j]==0时。说明p[j]是i的最小质因子, 那么p[j]一定也是p[j]*i的最小质因子
// 2. 当i%p[j]!=0时, 说明p[j]比i的最小质因子还小, 那么p[j]一定是p[j]*i的最小质因子
  • 时间复杂度:O(N)O(N)

质数

  • 定义:大于1,且除了1和它本身之外不再有其他因数的自然数。
  • 质数分布定理:11~nn间的质数大概有π(n)=nlnn\pi(n)=\frac{n}{\ln n}

互质数:两个或多个整数的公因数只有1的非0自然数。

  • 小性质:最小的9个质数相乘,答案在int范围内。

约数

1. 试除法求约数

(1) 求所有的质因数
1
2
3
4
5
6
7
8
9
10
11
void div(int x){
for (int i=2;(ll)i*i<=x;++i){
int cnt = 0;
while (x%i==0){
x /= i; cnt++;
}
if (cnt) printf("%d %d\n", i, cnt);
}
if (x > 1) printf("%d %d", x, 1);
puts("");
}
(2) 求所有的约数

使用筛法先筛质数,再通过dfs枚举约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int n, cnt, tot, dn;
const int N = 5e4 + 5;
bool st[N];
int p[N], d[N];
pii f[N];

void dfs(int u, int x){
if (u > tot){
d[++dn] = x; return ;
}
for (int i=0;i<=f[u].yy;++i){
dfs(u + 1, x);
x *= f[u].xx;
}
}

void solve(){
int a0, a1, b0, b1;
scanf("%d%d%d%d", &a0, &a1, &b0, &b1);
int n = b1;
tot = 0;
for (int i=1;p[i]<=n/p[i];++i){
if (n % p[i] != 0) continue;
int sm = 0;
while (n % p[i] == 0) n /= p[i], ++sm;
f[++tot] = pii(p[i], sm);
}
if (n > 1) f[++tot] = pii(n, 1);
dn = 0;
dfs(1, 1);
}

2. 约数个数

任何一个正整数nn都可以表达为如下形式:

n=p1a1×p2a2×...×pkakn=p_1^{a_1}\times p_2^{a_2}\times ...\times p_k^{a_k},其中,i[1,k],pi\forall i\in [1,k], p_i为质数

那么,对于nn的任意约数α\alpha,都可以将α\alpha写成如下形式:

α=p1b1×p2b2×...×pkbk\alpha=p_1^{b_1}\times p_2^{b_2}\times ...\times p_k^{b_k},其中,i[1,k]\forall i\in [1,k]0biak0\leq b_i \leq a_k

那么对于每一个bib_i,都有(ai+1)(a_i+1)种取法,因此,nn的所有约数之和为(a1+1)(a2+1)...(ak+1)(a_1+1)(a_2+1)...(a_k+1)

  • 小性质:所有int范围内的数,约数之和最多的约为1500

小例子:求n!的约数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int n, cnt;
const int N = 1e6 + 5;
int p[N], num[N];
bool st[N];

void Euler(int n){
for (int i=2;i<=n;++i){
if (!st[i]) p[++cnt] = i;
for (int j=1;p[j]<=n/i;++j){
st[p[j] * i] = true;
if (i % p[j] == 0) break;
}
}
}

int main(void){
scanf("%d", &n);
Euler(N - 1);
for (int i=2;i<=n;++i){
if (st[i]) continue;
for (ll j = i;j<=n;j*=i){
num[i] += n / j;
}
}
for (int i=2;i<=n;++i){
if (num[i]){
printf("%d %d\n", i, num[i]);
}
}

return 0;
}

3. 约数之和

αi=(p10+p11+...+p1a1)(p20+p21+...+p2a2)...(pk0+pk1+...+pkak)\sum \alpha_i=(p_1^0+ p_1^1+ ...+ p_1^{a_1})(p_2^0+ p_2^1+ ...+ p_2^{a_2})...(p_k^0+ p_k^1+ ...+ p_k^{a_k})

展开该式子,就可以得到α=p1b1×p2b2×...×pkbk\alpha=p_1^{b_1}\times p_2^{b_2}\times ...\times p_k^{b_k},所有的bib_i取值的组合相加。实际上,这个式子展开一共有(a1+1)(a2+1)..(ak+1)(a_1+1)(a_2+1)..(a_k+1)项,也对应了约数个数。

4. 欧几里得算法

欧几里得算法基于的性质:

  1. da,abd|a, a|b,则d(ax+by)d|(ax+by)

  2. (a,b)=(b,a mod b)(a,b)=(b,a~mod~b)

第二条性质证明:

a mod b=aab×b\because a~mod~b=a-\lfloor \frac{a}{b} \rfloor\times b,令c=abc=\lfloor \frac{a}{b} \rfloor

则问题等价于证明(a,b)=(b,ac×b)(a,b)=(b,a-c\times b)

这个证明方法就和裴蜀定理的证明差不多。

证明:令d=gcd(a,b)d=gcd(a,b),则da,dbd|a,d|b,易得d(ac×b)d|(a-c\times b)。则ddb,(ac×b)b,(a-c\times b)的公因数。

那么令D=(b,ac×b)D=(b,a-c\times b)dDd\leq D

Db,D(ac×b)D|b,D|(a-c\times b),易得DaD|a,则D(a,b)=dD\leq (a,b)=d

因此d=Dd=D,即d=gcd(b,ac×b)d=gcd(b,a-c\times b)

欧几里得算法模板

1
2
3
int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}

欧拉函数

1. 欧拉函数的定义

  • 定义φ(N)\varphi(N)11~NN中与NN互质的数,假设NN可以表达为p1a1×p2a2...pkakp_1^{a_1}\times p_2^{a_2}...p_k^{a_k}i[1,k],pi\forall i\in [1,k], p_i为质数,ai>0a_i>0

    φ(N)=N×(11p1)×(11p2)...(11pk)\varphi(N)=N\times (1-\frac{1}{p_1})\times(1-\frac{1}{p_2})...(1-\frac{1}{p_k})

特别的,规定φ(1)=1\varphi(1)=1。(唯一和1互质的数就是1本身)

证明:容斥原理

  1. 先去掉1~N中p1p_1的倍数,再去掉1~N中p2p_2的倍数,……直到去掉1~N中pkp_k的倍数。那么,此时答案就是

    NNp1Np2...NpkN-\frac{N}{p_1}-\frac{N}{p_2}-...-\frac{N}{p_k}

  2. 这个答案,将pi×pj,(i,j[1,k],ij)p_i\times p_j, (i,j\in[1,k], i\neq j)重复减去了多次,需要把它们加回来

    NNp1Np2...Npk+Np1p2+Np1p3+...+Npk1pkN-\frac{N}{p_1}-\frac{N}{p_2}-...-\frac{N}{p_k}+\frac{N}{p_1p_2}+\frac{N}{p_1p_3}+...+\frac{N}{p_{k-1}p_k}

  3. 考虑这样的三元组papbpcp_ap_bp_c,它们先是被1中的式子pa,pb,pcp_a,p_b,p_c减去了三次,又在2中的式子papb,papc,pbpcp_ap_b,p_ap_c,p_bp_c中加了三次,总体没加也没减。因此要把三元组的倍数从NN中减去

    NNp1Np2...Npk+Np1p2+Np1p3+...+Npk1pkNp1p2p3...Npk2pk1pkN-\frac{N}{p_1}-\frac{N}{p_2}-...-\frac{N}{p_k}+\frac{N}{p_1p_2}+\frac{N}{p_1p_3}+...+\frac{N}{p_{k-1}p_k}-\frac{N}{p_1p_2p_3}-...-\frac{N}{p_{k-2}p_{k-1}p_{k}}

  4. 以此类推,最终化简上面的式子,可得

    N×(11p1...1pk+1p1p2+...+1pk1pk...)=N×(11p1)×(11p2)...(11pk)N\times(1-\frac{1}{p_1}-...-\frac{1}{p_k}+\frac{1}{p_1p_2}+...+\frac{1}{p_{k-1}p_k}-...)\\=N\times (1-\frac{1}{p_1})\times(1-\frac{1}{p_2})...(1-\frac{1}{p_k})

  • 时间复杂度:欧拉函数时间复杂度最大的地方在于分解质因数,因此时间复杂度为O(N)O(\sqrt N)

欧拉函数模板

1
2
3
4
5
6
7
8
9
10
11
int phi(int x){
int res = x;
for (int i=2;(ll)i*i<=x;++i){
if (x % i == 0){
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
}
if (x > 1) res = res / x * (x - 1);
return res;
}

2. 欧拉函数的性质

性质1
  • a=n×φ(n)2,n>1,a[1,n),(a,n)=1\sum a=\frac{n\times \varphi(n)}{2}, n>1, a\in[1,n),(a,n)=1
性质2
  • n>2,φ(n)\forall n>2,\varphi(n)为偶数。

证明:(n,x)=(n,nx),n>x\because (n,x)=(n,n-x), n>x

假设x[1,n)\exist x\in[1,n)(n,x)=(n,nx)=1,x=nx,n>2(n,x)=(n,n-x)=1,x=n-x, n>2,则n=2xn=2x,矛盾。

[1,n)\therefore[1,n)中与nn互质的数均是成对出现的,因此[1,n)[1,n)nn互质的数是偶数,即φ(n)\varphi(n)为偶数。

观察(n,x)=(n,nx)=1(n,x)=(n,n-x)=1,也说明了任意一对与nn互质的数,相加均为nn,所以有a=n×φ(n)2\sum a = \frac{n\times\varphi(n)}{2}

性质3
  • dnφ(d)=n\sum\limits _{d|n} \varphi(d)=n

f(n)=φI=dnφ(d)f(n)=\varphi * I=\sum\limits _{d|n}\varphi(d),则f(n)f(n)为一个积性函数。

nn唯一分解为n=i=1kpiai=p1a1p2a2..pkakn= \prod_{i=1}^kp_i^{a_i} = p_1^{a_1}p_2^{a_2}..p_k^{a_k},则

f(piai)=φ(1)+φ(pi)+..+φ(piak)=1+(p1)+..+(pkpk1)=pkf(p_i^{a_i})=\varphi(1)+\varphi(p_i)+..+\varphi(p_i^{a_k})\\=1+(p-1)+..+(p^k-p^{k-1})=p^k

f(n)=f(p1a1)×f(p2a2)×..×f(pkak)=i=1kpiai=nf(n)=f(p_1^{a_1})\times f(p_2^{a_2})\times ..\times f(p_k^{a_k})=\prod_{i=1}^kp_i^{a_i}=n,证毕。

性质4
  • 欧拉函数为积性函数,但不是完全积性函数,当(n,m)=1(n,m)=1时,满足φ(m×n)=φ(m)×φ(n)\varphi(m\times n)=\varphi(m)\times \varphi(n)。那么显然,当nn唯一分解后,φ(n)=i=1kφ(piai)\varphi(n)=\prod_{i=1}^k\varphi(p_i^{a_i})

证明:若(n,m)=1(n,m)=1,则n,mn,m没有相同的质因子,记nn的质因子个数为c1c_1mm的质因子个数为c2c_2,则

φ(n)×φ(m)=n×m×i=1c1(11pi)×i=1c2(11pi)=i=1c1+c2(11pi)=φ(n×m)\varphi(n)\times \varphi(m)=n\times m\times \prod_{i=1}^{c_1}(1-\frac 1 {p_i})\times \prod_{i=1}^{c_2}(1-\frac 1 {p_i})=\prod_{i=1}^{c_1+c2}(1-\frac 1 {p_i})=\varphi(n\times m)

例题:cf776E The Holmes Children

性质5
  • φ(n)n=dnμ(d)d\frac {\varphi(n)} n=\sum\limits_{d\mid n}\frac{\mu(d)}{d}

写成狄利克雷卷积的形式

φI=id\varphi * I=idφIμ=idμ\varphi * I * \mu=id * \mu

φ(Iμ)=idμ\varphi * (I * \mu)=id * \mu

φe=idμ\varphi*e=id*\mu

φ(n)=dnnd×μ(d)\varphi(n)=\sum\limits _{d|n}\frac n d\times \mu(d),也就是φ(n)n=dnμ(d)d\frac {\varphi(n)} n=\sum\limits_{d\mid n}\frac{\mu(d)}{d}

性质6

n=pkn=p^k时,φ(n)=pkpk1\varphi(n)=p^k-p^{k-1}

证明:当nn只有一个质因数时,φ(n)=pk×(11p)=pkpk1\varphi(n)=p^k\times(1-\frac 1 p)=p^k-p^{k-1}

3. 筛法求欧拉函数

假设目前已知φ(i)\varphi(i)的值,pjp_j为某一质数,求φ(i×pj)\varphi(i\times p_j)的值。

ii表示为p1a1×p2a2...pkakp_1^{a_1}\times p_2^{a_2}...p_k^{a_k}φ(i)=i×(11p1)×(11p2)...(11pk)\varphi(i)=i\times (1-\frac{1}{p_1})\times(1-\frac{1}{p_2})...(1-\frac{1}{p_k})

  1. i%pj==0i\%p_j==0时,i×pji\times p_j中不存在新的质因子

    φ(i×pj)=i×pj×(11p1)×(11p2)...(11pk)=φ(i)×pj\therefore \varphi(i\times p_j)=i\times p_j\times (1-\frac{1}{p_1})\times(1-\frac{1}{p_2})...(1-\frac{1}{p_k})=\varphi(i)\times p_j

  2. i%pj0i\%p_j\neq 0时,pjp_j为新的质因子

    \begin{align} & \therefore \varphi(i\times p_j)=i\times p_j\times (1-\frac{1}{p_1})\times(1-\frac{1}{p_2})...(1-\frac{1}{p_k})\times (1-\frac{1}{p_j})\\ & =\varphi(i)\times p_j\times(1-\frac{1}{p_j})\\ & =\varphi(i)\times(p_j-1) \end{align}

  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int n, cnt;
const int N = 1e6 + 10;
int E[N], p[N];
bool st[N];

void Eulers(){
E[1] = 1;
for (int i=2;i<=n;++i){
if (!st[i]){
p[++cnt] = i;
E[i] = i - 1;
}
for (int j=1;p[j]<=n/i;++j){
int t = p[j] * i;
st[t] = true;
if (i % p[j] == 0){
E[t] = E[i] * p[j];
break;
}
E[t] = E[i] * (p[j] - 1);
}
}
}

快速幂

1. 定义

1
2
3
4
5
6
7
8
9
10
// 求a^b % p 时间复杂度O(logN)
ll qmi(ll a, ll b, ll p){
ll res = 1LL % p;
while (b){
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}

2. 快速幂求逆元

乘法逆元的定义

​ 若对于整数b,mb,m,有(b,m)=1(b,m)=1(即b,mb,m互质),并且对于任意的整数aa,如果满足bab|a,则xN\exist x\in Ns.t.  ab=a×x(mod m)s.t.~~\frac{a}{b}=a\times x(mod~ m),则称xxbb的模mm乘法逆元,记为b1(mod m)b^{-1}(mod~m)

  • bb存在乘法逆元的充要条件是(b,m)=1(b,m)=1,当mm为质数时,bb的乘法逆元为bm2b^{m-2}

  • 小性质

    aba×x(mod m)\frac{a}{b} \equiv a\times x(mod ~m) aba×b1(mod m)\frac{a}{b} \equiv a\times b^{-1}(mod ~m)

    aa×b×b1(mod m)a\equiv a\times b \times b^{-1}(mod ~m)b×b11(mod m)b\times b^{-1} \equiv 1(mod ~m)

  • 费马小定理

    p\forall p为质数,aa为任意整数,有$ a^{p-1}\equiv 1(mod ~p)$

    小推论:b×bp21(mod p)b\times b^{p-2}\equiv 1(mod~p),因此bb的乘法逆元为bp2b^{p-2}

扩展欧几里得算法

1. 前置知识-裴蜀定理

裴蜀定理a,bZ\forall a,b\in \Z, 令d=(a,b)d=(a,b),那么对于任意的整数x,yZx,y\in \Zax+by=kdax+by=kd。特别的,一定x,y\exist x,y,使得ax+by=dax+by=d成立。

丢番图方程ax+by=max+by=m有解,当且仅当mmdd的倍数。丢番图方程有解时必然有无穷多个解,每组解x,yx,y都称为裴蜀数,可用辗转相除法求得。

证明:

(前半句)da,db\because d|a,d|bx,yZ,d(ax+by)\therefore \forall x,y\in Z, d|(ax+by)

(特别的…)设ssax+byax+by的最小正值,令 q=asq=\lfloor \frac{a}{s} \rfloorr=a mod sr=a ~mod ~s

r=aas×s=aq×(ax+by)=a(1qx)+b(qy)r=a-\lfloor \frac{a}{s} \rfloor\times s=a-q\times(ax+by)=a(1-qx)+b(-qy),即rr也为a,ba,b的线性组合

r=a mod s\because r=a~mod~s0r<s\therefore 0\leq r <s

ssax+byax+by的最小正值,可得r=0r=0,即a mod s=0a ~mod~s=0

sa\therefore s|a,再设r2=b mod sr_2=b~mod~s,同理可得sbs|b。因此ssa,ba,b的公因子,dsd\geq s

da,db,s=ax+by\because d|a,d|b,s=ax+byds\therefore d|sdsd\leq s

因此d=sd=s,命题得证。

推论1(a,b)=1(a,b)=1的充分必要条件是x,yZ,s.t.  ax+by=1\exist x,y\in Z, s.t.~~ax+by=1

推论2:裴蜀等式也可以用来给最大公约数定义:dd其实就是最小的可以写成ax+byax + by形式的正整数。

推论2:设a1,a2,...,ana_1,a_2,...,a_nnn个整数,dd是它们的最大公约数,那么x1,x2,...,xn\exist x_1,x_2,...,x_n,使得a1x1+a2x2+...+anxn=da_1x_1+a_2x_2+...+a_nx_n=d成立。特别的,若a1,a2,...,ana_1,a_2,...,a_n是互质的(不是两两互质),那么x1,x2,...,xn\exist x_1,x_2,...,x_n,使得a1x1+a2x2+...+anxn=1a_1x_1+a_2x_2+...+a_nx_n=1成立。

2. 扩展欧几里得算法

如何用扩展欧几里得算法求裴蜀数?

假如要求解的不定方程(又名丢番图方程)为ax+by=max+by=m

我们现在先求解不定方程ax+by=dax+by=d,其中d=(a,b)d=(a,b)dmd|m

由欧几里得算法性质1,2可知(a,b)=(b,a mod b)=(b,aab×b)(a,b)=(b,a~mod~b)=(b, a-\lfloor \frac{a}{b} \rfloor\times b)

ax1+by1=dax_1+by_1=d有解,则by2+(a mod b)x2=dby_2+(a~mod~b)x_2=d一定有解,即by2+(aab×b)x2=dby_2+(a-\lfloor \frac{a}{b} \rfloor\times b)x_2=d有解。

化简得ax2+b(y2ab×x2)=dax_2+b(y_2-\lfloor \frac{a}{b} \rfloor\times x_2)=d,那么x1=x2,y1=y2ab×x2x_1=x_2,y_1=y_2-\lfloor \frac{a}{b} \rfloor\times x_2

于是可以递归进行操作,当b=0b'=0时,(a,0)=d(a',0)=d,也就是a=da'=d,此时x=1,y=0x=1,y=0为一组平凡解,再不断带回,即可得到不定方程的一组特解,设此特解为{x1,y1}\{x_1,y_1\}。则通解即为{x1+k×bd,y1k×ad,kZ}\{x_1+k\times\frac{b}{d}, y_1-k\times\frac{a}{d}, k\in \Z\}

证明通解是方程的解:

ax+by=a×(x1+k×bd)+b×(y1k×ad)=ax1+by1+k×(abdabd)=dax+by=a\times(x_1+k\times\frac{b}{d})+b\times(y_1-k\times\frac{a}{d})\\=ax_1+by_1+k\times (\frac{ab}{d}-\frac{ab}{d})=d

因此,通解是可以使等式成立的。

那么同理,ax+by=max+by=m,通解也是{x0+k×bd,y0k×ad}\{x_0+k\times \frac{b}{d}, y_0-k\times \frac{a}{d}\}

  • 代码
1
2
3
4
5
6
7
8
9
int exgcd(int a, int b, int &x, int &y){
if (!b){
x = 1, y = 0;
return a;
}
int d = exgcd(b, a%b, y, x);
y -= a / b * x;
return d;
}

同余

1. 定义

如果a,bZa,b\in\Z,而mm是一个固定的正整数,则当m(ab)m|(a-b)时,我们就说a,ba,b对模mm同余,记作ab(modm)a\equiv b(\mod m),当mm不能整除aba-b时,我们就说a,ba,b对模mm不同余,记作a≢b(modm)a \not\equiv b(\mod m)

2. 运算法则

{A×B mod P=(A mod P×B mod P)modP(A+B) mod P=(A mod P+B mod P)modP(AB) mod P=(A mod PB mod P+P)modPcnt(x)=__bulitin_popcount(x),cnt(AB) mod 2=cnt(A) mod2 cnt(B)mod2AB(mod P)AnBnmodm\begin{cases} A\times B~mod ~P = (A ~mod ~P \times B ~mod ~P) \mod P\\ (A + B)~ mod~ P = (A ~mod ~P + B ~mod ~P) \mod P \\ (A - B)~ mod ~P = (A ~mod~ P - B ~mod ~P + P) \mod P \\ 令cnt(x)=\_\_bulitin\_popcount(x), 则\\ cnt(A \oplus B) ~mod ~2 = cnt(A)~mod 2~ \oplus cnt(B)\mod 2 \\ A\equiv B(mod~P) \rightarrow A^n\equiv B^n \mod m \end{cases}

3. 基本概念

(1) 剩余类 完全剩余系 和 简化剩余系

  • 剩余类:也叫同余类,设模为nn,则根据余数可将所有的整数分为nn类,把所有和整数aann同余的整数构成的集合叫做模nn的一个剩余类,记作[a][a],并把aa叫做剩余类[a][a]的一个代表元。
  • 完全剩余系:从模nn的每个剩余类中各取一个数,得到一个由nn个数组成的集合,叫做模nn的一个完全剩余系。最常用的完全剩余系是{0,1,...,n1}\{0,1,...,n-1\}
  • 简化剩余系:也称既约剩余系或缩系,是nn的完全剩余系中与nn互质的数构成的子集。如果模nn的一个剩余类里所有数都与nn互质,就把它叫做与模nn互质的剩余类。在与模nn互质的全体剩余类中,从每个类中各任取一个数作为代表组成的集合,叫做模nn的一个简化剩余系。

4. 常用小定理

  • **定理1:**如果a,b,ca,b,c是任意三个整数,mm是一个正整数且(m,c)=1(m,c)=1,则当acbc(modm)ac\equiv bc(\mod m)时,有ab(modm)a\equiv b(\mod m)

证明:由于c(ab)=acbc=mqc(a-b)=ac-bc=mq,其中qZq\in \Z(m,c)=1(m,c)=1。我们有ab=mqc=mq1a-b=m\frac{q}{c}=mq_1

  • **定理2:**满足ax1(modm)a^{x}\equiv 1(\mod m)的最小正整数xx,一定是φ(m)\varphi(m)的约数,即xφ(m)x|\varphi(m)

反证法。假设x∤φ(m),φ(m)=qx+r,r(0,x)x\not\mid \varphi(m),\varphi(m)=qx+r, r\in(0,x)

则有aqx1q(modm)a^{qx}\equiv 1^q(\mod m)aqx+r1(modm)a^{qx+r}\equiv 1(\mod m)

ar1(modm)a^r\equiv 1(\mod m)r<xr<x,又xx是满足同余式的最小正整数,矛盾。得证。

  • 定理3x>0\exist x>0,使得ax1(modm)a^x\equiv 1(\mod m)成立,它的充分必要条件为(a,m)=1(a,m)=1

必要性:即欧拉定理aφ(m)1(modm)a^{\varphi(m)}\equiv 1(\mod m)的证明;

充分性:(反证法)若ax1(modm),x>0a^x\equiv 1(\mod m),x>0,则ax+k×m=1a^x+k\times m=1,若(a,m)=w>1(a,m)=w>1,则ax+k×m=w×ax+k×mww>1a^x+k\times m=w\times\frac{a^x+k\times m}{w}\geq w>1。矛盾,得证。

同余这块,有非常多乱七八糟的构造方法,非常偏数学,甚至可以做到《初等数论》上的题目……只能说注意积累,大胆乱猜

初等数论四大定理

1. 威尔逊定理

(1) 结论

当且仅当pp为素数时,(p1)!1(modp)(p-1)!\equiv -1(\mod p)

(2) 证明

充分性:若pp不为素数,则(p1)!≢1(modp)(p-1)!\not\equiv -1(\mod p)

  • p=4p=4时,显然(p1)!62(modp)(p-1)!\equiv 6\equiv 2(\mod p)

  • p>4p>4

    • pp为完全平方数,则k\exist k,使得p=k2p=k^2,由于p>4p>4,故k>2,2k<pk>2,2k<p(p1)!n(k×2k)2n×k20(modp)(p-1)!\equiv n(k\times2k)\equiv 2n\times k^2\equiv 0(\mod p)
    • pp不是完全平方数,则a,b,ab\exist a,b,a\neq b,使得ab=pab=p,则(p1)!nab0(modp)(p-1)!\equiv nab\equiv 0(\mod p)

必要性:若pp为素数,则一定有(p1)!1(modp)(p-1)!\equiv -1(\mod p)

p=2p=2时,结论显然成立。

pp为奇素数,取集合A={1,2,3,..,p1}A=\{1,2,3,..,p-1\}AA构成模pp乘法的简化剩余系,即iA,jA\forall i\in A,\exist j\in A,使得i×j1(modp)i\times j\equiv 1(\mod p)

证明:因为AA构成模pp乘法的取值的集合了(除了0),所以这个结论肯定成立。

那么,这p1p-1个数是不是两两配对的呢?首先,由同余的运算法则,可以得到一定没有ijik(modp),jkij\equiv ik(\mod p), j\neq k的情况,那么它一定是两个一对,或者单独一个的情况。考虑x21(modp)x^2\equiv 1(\mod p),解得x1(modp)x\equiv 1(\mod p),或者xp1(modp)x\equiv p-1(\mod p),那么其余则两两配对。因此(p1)!1×(p1)1(modp)(p-1)!\equiv 1\times (p-1)\equiv -1(\mod p),得证。

(5)例题

可以看下它的考察方式:UVA1434 YAPTCHA,主要就是欧拉筛+威尔逊定理+前缀和

image-20220717191118846

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int n, cnt;
const int N = 3e6 + 20;
bool st[N];
int p[N], pre[N];

void Euler(int n){
for (int i=2;i<=n;++i){
if (!st[i]) p[++cnt] = i;
for (int j=1;p[j]<=n/i;++j){
st[i * p[j]] = true;
if (i % p[j] == 0) break;
}
}
}

void init(){
Euler(N - 1);
for (int i=1;i<N;++i){
int x = 0;
if (i > 7 && (i - 7) % 3 == 0 && !st[i]){
x = 1;
}
pre[i] = pre[i - 1] + x;
}
}

int main(void){
init();
int t;
scanf("%d", &t);
while (t--){
scanf("%d", &n);
printf("%d\n", pre[n * 3 + 7]);
}
return 0;
}

2. 欧拉定理

(1) 结论

mm是一个大于1的整数,且满足条件(a,m)=1(a,m)=1,则我们有

aφ(m)1(modm)a^{\varphi(m)}\equiv 1(\mod m)

(2) 证明

引理1:mm是一个大于1的整数,aa是一个整数且满足(a,m)=1(a,m)=1,如果B={b1,b2,..,bφ(m)}B=\{b_1,b_2,..,b_{\varphi(m)}\}是模mm的一个简化剩余系,则B={ab1,ab2,..,abφ(m)}B'=\{ab_1,ab_2,..,ab_{\varphi(m)}\}也是模mm的一个简化剩余系。

证明:由于从BB中取出任何一个正整数bib_i,都有(bi,m)=1(b_i,m)=1。又(a,m)=1(a,m)=1,可以得到在BB'中任意取出一个整数abiab_i,都有(abi,m)=1(ab_i,m)=1。那么,现在利用反证法,假设在BB'中存在两个整数abk,abλab_k,ab_{\lambda}1k<λφ(m)1\leq k < \lambda \leq \varphi(m),使得:abkabλ(modm)ab_k\equiv ab_{\lambda}(\mod m)成立。

(a,m)=1(a,m)=1,故bkbλ(modm)b_k\equiv b_{\lambda}(\mod m),由于bk,bλb_k,b_{\lambda}是简化剩余系的元素,因此不可能模mm同余,所以同余等式不可能成立,得证。

下面正式的证明欧拉定理。

考虑模mm的最小正缩系AA,即A={1,a2,...,aφ(m)}A=\{1,a_2,...,a_{\varphi(m)}\},是不大于mm且和mm互质的全体正整数,令r1r_1是一个整数,满足条件:$ a \times 1\equiv r_1(\mod m), r_1\in[0,m-1]$

rir_i(其中i=2,..,φ(m)i=2,..,\varphi(m))是一个整数,满足条件:aairi(modm),ri[0,m1]aa_i\equiv r_i(\mod m),r_i\in[0,m-1]

则我们有ar1(modm),aa2r2(modm),..,aaφ(m)rφ(m)(modm)a\equiv r_1(\mod m),aa_2\equiv r_2(\mod m),..,aa_{\varphi(m)}\equiv r_{\varphi(m)}(\mod m)

由于AA是模mm的一个简化剩余系,并且(a,m)=1(a,m)=1,因此R={r1,r2,..,rφ(m)}R=\{r_1,r_2,..,r_{\varphi(m)}\}也是一个简化剩余系,并且和AA至少在次序上可能有不同,故得到i=1φ(m)ri=i=1φ(m)ai\prod_{i=1}^{\varphi(m)}r_i=\prod_{i=1}^{\varphi(m)}a_i

因此i=1φ(m)(a×ai)i=1φ(m)ai(modm)\prod_{i=1}^{\varphi(m)}(a\times a_i) \equiv \prod_{i=1}^{\varphi(m)}a_i (\mod m)

aφ(m)1(modm)a^{\varphi(m)}\equiv 1(\mod m)

(3) 推论

欧拉降幂:
  • AbAbmodφ(m)(modm)A^b\equiv A^{b\mod \varphi(m)} (\mod m)

证明:设b=k×φ(m)+rb=k\times \varphi(m)+r,则r=bmodφ(m)r=b\mod \varphi(m)

AbAr×(Aφ(m))kAr(modm)A^b\equiv A^r\times (A^{\varphi(m)})^k\equiv A^r(\mod m)