参考 smwcDay9 PPT by lby。
待补列表：
- 中国剩余定理的证明
- 欧拉定理（扩展）
- 埃氏筛的时间复杂度证明 O ( n l o g l o g n ) O(nloglogn) O(nloglogn) ？
- 扩展中国剩余定理 e x c r t excrt excrt 的证明？ （from [CF 687B] Remainders Game)
目录
- 整除
- 性质
- [CF 762A] k-th divisor
- 质数与合数
- [CF 776B] Sherlock and his girlfriend
- 带余除法，同余
- 最大公约数（gcd）
- 性质
- [CF 664A] Complicated GCD
- [CF 757B] Bash's Big Day
- 欧几里德算法
- 裴蜀定理
- 推论
- 扩展欧几里德算法（exgcd）
- LG P4549 【模板】裴蜀定理
- 逆元
- 推论
- 中国剩余定理（CRT）
- 例题：组合数取模2
- 欧拉函数
- [SDOI2012]Longge的问题
- [Sdoi2008]沙拉公主的困惑
- 欧拉定理
- 欧拉定理的扩展
- LG P4139 上帝与集合的正确用法
- 线性筛与积性函数
- LG P2568 GCD
- 例题2
- 补充题
- [SDOI2009] SuperGCD
- [Violet 5] 樱花
- [CF 632D] Longest Subsequence
- [CF 582A] GCD Table
- [CF 687B] Remainders Game
- 总结
整除
a , b a,b a,b 都为整数，若 a a a 被 b b b 整除，相当于 b b b 整除 a a a，则记 b ∣ a b \, | \,a b∣a ，就有 b b b 是 a a a 的因数， a a a 是 b b b 的倍数。
性质
- 若 a ∣ b , a ∣ c a \,|\,b\;, a\, | \, c a∣b,a∣c，则 a ∣ ( b + c ) , a ∣ ( b − c ) a\,| \,(b+c) \;, a\,| (b-c) a∣(b+c),a∣(b−c) ；
- 若 a ∣ b , b ∣ c a \,|\,b\;, b\, | \, c a∣b,b∣c，则 a ∣ c a\,| \,c a∣c ;
[CF 762A] k-th divisor
link
题意
求
n
n
n 的第
k
k
k 小的约数，如果不存在输出
−
1
-1
−1 。
1
≤
n
≤
1
0
15
,
1
≤
k
≤
1
0
9
1 \le n \le 10^{15}, 1 \le k \le 10^9
1≤n≤1015,1≤k ≤ 109
思路
枚举
n
n
n 的因数即可，找
1
1
1 ~
n
\sqrt{n}
n 的因数，就能对应的找到
>
n
\gt \sqrt{n}
>n 的因数，时间复杂度为
O
(
n
)
O(\sqrt{n})
O(n) 。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+5;
ll g[maxn];
int main(){
ll n,k; cin>>n>>k; int cnt=0;
for(ll i=1;i*i<=n;i++)
if(n%i==0){
g[++cnt]=i;
if(cnt==k){
cout<<i;
return 0;
}
}
for(int i=cnt;i>=1;i--)
if(n/g[i]!=g[i]){
cnt++;
if(cnt==k){
cout<<n/g[i];
return 0;
}
}
cout<<"-1";
return 0;
}
质数与合数
1
1
1 既不是质数也不是合数。
不大于
n
n
n 的质数约有
n
ln
(
n
)
\frac{n}{\ln(n)}
ln(n)n 个。
唯一分解定理：把正整数
n
n
n 写成质数的乘积（即
n
=
p
1
e
1
×
p
2
e
2
×
p
3
e
3
×
⋯
×
p
k
e
k
n=p_{1}^{e_1} \times p_{2}^{e_2} \times p_{3}^{e_3}\times \dots \times p_{k}^{e_k}
n=p1e1×p2e2×p3e3×⋯×pkek，其中
p
p
p 为质数且单调递增），这样的表示是唯一的。
[CF 776B] Sherlock and his girlfriend
link
题意
n
n
n 个点，标号为
2
…
n
+
1
2\dots n+1
2…n+1，将点染色，若
a
a
a 是
b
b
b 的质因子（
a
≠
b
a\not= b
a=b），则
a
a
a 和
b
b
b 的颜色不同，求一种颜色数最少的方案。
n
≤
1000
n \le 1000
n≤1000
思路
考虑将质数分在一个集合，合数分在另一个集合，分别染上不同颜色即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
bool isprm[maxn];
int main(){
int n; cin>>n;
cout<<(n<=2?"1\n":"2\n");
for(int i=2;i<=n+1;i++){
if(!isprm[i]) cout<<"1 ";
else cout<<"2 ";
for(int j=i+i;j<=n+1;j+=i)
isprm[j]=1;
}
return 0;
}
带余除法，同余
对于整数
a
,
b
a,b
a,b，
b
>
0
b>0
b>0，则存在唯一的整数
q
,
r
q,r
q,r，满足
a
=
b
q
+
r
a=bq+r
a=bq+r。（
r
=
a
m
o
d
b
r=a \,mod \, b
r=amodb）
若两数
a
,
b
a,b
a,b 除以
c
c
c 的余数相等，则称
a
,
b
a,b
a,b 模
c
c
c 同余，记做
a
≡
b
(
m
o
d
c
)
a≡b\;(mod\,c)
a≡b(modc) 。
性质：
a
≡
b
(
m
o
d
c
)
a≡b\;(mod\,c)
a≡b(modc) 等价于
c
∣
(
a
−
b
)
c\,|\,(a-b)
c∣(a−b)
最大公约数（gcd）
对于两个的整数
a
,
b
a,b
a,b，一般记
g
c
d
(
a
,
b
)
=
(
a
,
b
)
gcd(a,b)=(a,b)
gcd(a,b)=(a,b) 。
求最大公约数：
a
=
p
1
a
1
p
2
a
2
…
p
k
a
k
，
b
=
p
1
b
1
p
2
b
2
…
p
k
b
k
a=p_{1}^{a_1}p_{2}^{a_2} \dots p_{k}^{a_k}，b=p_{1}^{b_1}p_{2}^{b_2} \dots p_{k}^{b_k}
a=p1a1p2a2…pkak，b=p1b1p2b2…pkbk，有
(
a
,
b
)
=
p
1
m
i
n
(
a
1
,
b
1
)
p
2
m
i
n
(
a
2
,
b
2
)
…
p
k
m
i
n
(
a
k
,
b
k
)
(a,b)=p_{1}^{min(a_1,b_1)}p_{2}^{min(a_2,b_2)} \dots p_{k}^{min(a_k,b_k)}
(a,b)=p1min(a1,b1)p2min(a2,b2)…pkmin(ak,bk) 。
性质
- ( 0 , a ) = a (0,a)=a (0,a)=a
- ( a , b ) = ( a , a + b ) = ( a , k a + b ) (a,b)=(a,a+b)=(a,ka+b) (a,b)=(a,a+b)=(a,ka+b)
- ( k a , k b ) = k ⋅ ( a , b ) (ka,kb)=k \cdot (a,b) (ka,kb)=k⋅(a,b)
- ( a , b , c ) = ( ( a , b ) , c ) (a,b,c)=((a,b),c) (a,b,c)=((a,b),c)
[CF 664A] Complicated GCD
link
题意
求
g
c
d
(
a
,
a
+
1
,
a
+
2
,
…
,
b
)
gcd(a,a+1,a+2, \dots , b)
gcd(a,a+1,a+2,…,b) 。
1
≤
a
≤
b
≤
1
0
100
1≤a≤b≤10^{100}
1≤a≤b≤10100
思路
注意到
g
c
d
(
a
,
a
+
1
)
=
1
gcd(a,a+1)=1
gcd(a,a+1)=1 ，所以答案为
1
1
1，注意特判
a
=
b
a=b
a=b 的情况。
[CF 757B] Bash’s Big Day
link
题意
给定
n
n
n 个正整数
{
a
i
}
\{a_i\}
{ai}，求一个子集
S
S
S，满足
g
c
d
(
S
1
,
S
2
,
.
.
.
,
S
k
)
>
1
gcd(S_1,S_2, ...,S_k)>1
gcd(S1,S2,...,Sk)>1，同时
∣
S
∣
|S|
∣S∣ 尽可能大。
1
≤
n
,
a
i
≤
1
0
5
1≤n,a_i≤10^5
1≤n,ai≤105
思路
考虑枚举
d
=
g
c
d
d = gcd
d=gcd ，此时符合条件的集合为
{
d
,
2
d
,
3
d
…
}
\{d,2d,3d\dots\}
{d,2d,3d…} 。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int v[maxn];
bool isprm[maxn];
int main(){
int n; cin>>n; int ma=0;
for(int i=1;i<=n;i++){
int a; cin>>a;
v[a]++,ma=max(ma,a);
}
int ans=1;
for(int i=2;i<=ma;i++){
if(isprm[i]) continue;
int s=0;
for(int j=i;j<=ma;j+=i)
isprm[j]=1,s+=v[j];
ans=max(ans,s);
}
cout<<ans;
return 0;
}
欧几里德算法
又称为辗转相除法，用于快速计算两数的
g
c
d
gcd
gcd 的算法。
由性质
(
a
,
b
)
=
(
a
,
k
a
+
b
)
(a,b)=(a,ka+b)
(a,b)=(a,ka+b) 得到：
(
a
,
b
)
=
(
b
,
a
m
o
d
b
)
\color{red}{(a,b)=(b,a\,mod\,b)}
(a,b)=(b,amodb)
时间复杂度是
O
(
l
o
g
n
)
O(logn)
O(logn) 。
裴蜀定理
设
(
a
,
b
)
=
d
(a,b)=d
(a,b)=d ，则对任意整数
x
,
y
x,y
x,y ，有
d
∣
(
a
x
+
b
y
)
d\,|\,(ax+by)
d∣(ax+by) 成立；特别地，一定存在
x
,
y
x,y
x,y 满足
a
x
+
b
y
=
d
ax+by=d
ax+by=d 。
相当于
a
x
+
b
y
=
c
ax+by=c
ax+by=c（
a
,
b
,
c
a,b,c
a,b,c 均为整数）有解的充要条件是
(
a
,
b
)
∣
c
(a,b)\,|\,c
(a,b)∣c 。
推论
a , b a,b a,b 互质等价于 a x + b y = 1 ax+by=1 ax+by=1 有解。（即 c = 1 c=1 c=1 的情况）
扩展欧几里德算法（exgcd）
有 ( a , b ) = d (a,b)=d (a,b)=d，求解 a x + b y = d ax+by=d ax+by=d 。
- 求其中一组解：
根据带余除法的定义，记 a = b q + r a=bq+r a=bq+r 。原方程可转化成 b x + r y = d bx+ry=d bx+ry=d （类似于辗转相除， g c d ( a , b ) = g c d ( b , a m o d b ) gcd(a,b)=gcd(b,a\,mod\,b) gcd(a,b)=gcd(b,amodb)）。记新方程的一个解为 x = x 0 , y = y 0 x=x_0,y=y_0 x=x0,y=y0，考虑如何推回原方程的解。
将 a = b q + r a=bq+r a=bq+r 代入原方程 a x + b y = d ax+by=d ax+by=d 中，化简得 ( q x + y ) b + r x = d (qx+y)b+rx=d (qx+y)b+rx=d，令 q x + y = x 0 , x = y 0 qx+y=x_0,x=y_0 qx+y=x0,x=y0，上式成立。
故 x = y 0 , y = x 0 − q × y 0 x=y_0,y=x_0-q\times y_0 x=y0,y=x0−q×y0 即为原方程的解。注意当 b = 0 b=0 b=0 时，令 x = 1 , y = 0 x=1,y=0 x=1,y=0。 - 求所有解：
因为我们已经有了一组解 x 0 , y 0 x_0,y_0 x0,y0，令 d x = b ( a , b ) , d y = − a ( a , b ) d_x=\frac{b}{(a,b)},d_y=-\frac{a}{(a,b)} dx=(a,b)b,dy=−(a,b)a。
则所有解就是 x = x 0 + k d x , y = y 0 + k d y x=x_0+kd_x,y=y_0+kd_y x=x0+kdx,y=y0+kdy， k k k 取任意整数。
LG P4549 【模板】裴蜀定理
link
题意
给定整数
{
a
1
,
a
2
,
a
3
,
.
.
.
,
a
n
}
\{a_1, a_2, a_3, ..., a_n\}
{a1,a2,a3,...,an} 和
k
k
k ，有一个待定整数序列
x
1
,
x
2
,
x
3
,
.
.
.
,
x
n
{x_1, x_2, x_3, ..., x_n}
x1,x2,x3,...,xn，满足
a
1
x
1
+
a
2
x
2
+
a
3
x
3
+
.
.
.
+
a
n
x
n
=
k
a_1x_1+a_2x_2+a_3x_3+...+a_nx_n=k
a1x1+a2x2+a3x3+...+anxn=k，求
k
>
0
k \gt 0
k>0 且
k
k
k 尽量小。
1
≤
n
≤
20
,
∣
A
i
∣
≤
1
0
5
1≤n≤20,|A_i|≤10^5
1≤n≤20,∣Ai∣≤105
思路
根据裴蜀定理，有
g
c
d
(
a
1
,
a
2
,
a
3
,
…
,
a
n
)
∣
k
gcd(a_1,a_2,a_3,\dots,a_n) \,| k
gcd(a1,a2,a3,…,an)∣k ，所以
k
m
i
n
=
g
c
d
(
a
1
,
a
2
,
…
,
a
n
)
k_{min}=gcd(a_1,a_2,\dots,a_n)
kmin=gcd(a1,a2,…,an) 。
逆元
若
a
x
≡
1
(
m
o
d
b
)
ax≡1 \,(mod\,b)
ax≡1(modb)，则称
x
x
x 是
a
a
a 关于模
b
b
b 的逆元，常记做
a
−
1
a^{-1}
a−1。
根据同余的性质，上式等价于
a
x
+
b
y
=
1
ax+by=1
ax+by=1，如何求逆元？等价于解方程
a
x
+
b
y
=
1
ax+by=1
ax+by=1 。
因此逆元不一定存在：存在的充要条件为
(
a
,
b
)
=
1
(a,b)=1
(a,b)=1 。
推论
p 是质数， p 不整除 a ，则 a 模 p 的逆元存在。 \color{red}{p \,是质数，p\, 不整除\, a ，则 \,a\, 模 \,p\, 的逆元存在。} p是质数，p不整除a，则a模p的逆元存在。
结论：在 [ 0 , b ) [0,b) [0,b) 的范围内， a a a 关于模 b b b 的逆元（若存在）是唯一的。（证明可考虑反证法）
如何 O ( n ) O(n) O(n) 求 1 1 1 ~ n n n 模质数 p p p 的逆元 ？
- 方法一：倒推
先求出 n ! n! n! 的逆元，然后利用 ( k − 1 ) ! − 1 ≡ k × k ! − 1 ( m o d p ) (k-1)!^{-1}≡k\times k!^{-1} \,(mod \,p) (k−1)!−1≡k×k!−1(modp)，倒推求出 1 ! … ( n − 1 ) ! 1!\dots(n-1)! 1!…(n−1)! 的逆元，再利用 k − 1 ≡ ( k − 1 ) ! k ! − 1 ( m o d p ) k^{-1}≡(k-1)!\,k!^{-1} \,(mod\,p) k−1≡(k−1)!k!−1(modp)，就可以求出 1... n 1...n 1...n 的逆元了。 - 方法二：递推
现在求 i i i 的逆元，考虑带余除法，设 p = i q + r p=iq+r p=iq+r ，则有 i q + r ≡ 0 ( m o d p ) iq+r≡0 \,(mod \,p) iq+r≡0(modp)，注意到 p p p 是质数，因此 r r r 不为0， r r r 的逆元存在。等式两边乘 i − 1 r − 1 i^{-1} r^{-1} i−1r−1，得到 q r − 1 + i − 1 ≡ 0 ( m o d p ) qr^{-1}+i^{-1}≡0 \,(mod\,p) qr−1+i−1≡0(modp)，因此 i − 1 ≡ − q r − 1 ≡ − n i ( p m o d i ) − 1 ( m o d p ) i^{-1}≡-qr^{-1}≡-\frac{n}{i}(p \,mod \,i)^{-1} \,(mod\,p) i−1≡−qr−1≡−in(pmodi)−1(modp) 。
inv[1]=1; for(int i=2;i<=n;i++) inv[i] = (- p / i + p) * inv[p % i] % p;
中国剩余定理（CRT）
形如
a
x
≡
c
(
m
o
d
b
)
ax≡c \,(mod \,b)
ax≡c(modb) 的方程，称为 线性同余方程。等价于
a
x
+
b
y
=
c
ax+by=c
ax+by=c，因此有解条件为
(
a
,
b
)
∣
c
(a,b)\,|\,c
(a,b)∣c 。
中国剩余定理：对于同余方程组
x
≡
a
i
(
m
o
d
m
i
)
(
i
=
1...
n
)
x≡a_i\,(mod \,m_i) (i=1...n)
x≡ai(modmi)(i=1...n)，若
m
i
m_i
mi 两两互质，则
x
x
x 在
m
o
d
M
mod \,M
modM下有唯一解。这里
M
=
m
1
m
2
.
.
.
m
n
M=m_1m_2...m_n
M=m1m2...mn 。
构造解的方法：
令
M
i
=
M
m
i
M_i=\frac{M}{m_i}
Mi=miM，显然
(
M
i
,
m
i
)
=
1
(M_i,m_i)=1
(Mi,mi)=1，所以
M
i
M_i
Mi 关于模
m
i
m_i
mi 的逆元存在，把这个逆元设为
t
i
t_i
ti。
于是有
M
i
t
i
≡
1
(
m
o
d
m
i
)
,
M
i
t
i
≡
0
(
m
o
d
m
j
)
(
j
≠
i
)
M_it_i≡1 \,(mod \,m_i),\; M_it_i≡0 \,(mod \,m_j) (j≠i)
Miti≡1(modmi),Miti≡0(modmj)(j=i) ，
进一步
a
i
M
i
t
i
≡
a
i
(
m
o
d
m
i
)
,
a
i
M
i
t
i
≡
0
(
m
o
d
m
j
)
(
j
≠
i
)
a_iM_it_i≡a_i\, (mod \,m_i), a_iM_it_i≡0 \,(mod \,m_j) (j≠i)
aiMiti≡ai(modmi),aiMiti≡0(modmj)(j=i) ，
因此解为
x
≡
a
1
M
1
t
1
+
a
2
M
2
t
2
+
.
.
.
+
a
n
M
n
t
n
(
m
o
d
M
)
x≡a_1M_1t_1+a_2M_2t_2+...+a_nM_nt_n\, (mod \,M)
x≡a1M1t1+a2M2t2+...+anMntn(modM) 。
例题：组合数取模2
题意
T
T
T 次询问，每次询问
C
(
n
,
k
)
m
o
d
1029471131
（
1029471131
=
13
×
317
×
249811
)
C(n, k) \,mod \,1029471131（1029471131 = 13\times 317\times 249811)
C(n,k)mod1029471131（1029471131=13×317×249811)
T
≤
1
0
5
,
0
≤
k
≤
n
≤
1
0
18
T≤10^5, 0≤k≤n≤10^{18}
T≤105,0≤k≤n≤1018
思路
分别将
C
(
n
,
k
)
C(n, k)
C(n,k) 对
13
,
317
,
249811
13, 317, 249811
13,317,249811 取模，再用中国剩余定理合并。
如何求
C
(
n
,
k
)
m
o
d
p
C(n, k)\,mod \,p
C(n,k)modp （其中
p
p
p 为较小的质数）？
∗
L
u
c
a
s
定理：
\color{red}{*Lucas定理：}
∗Lucas定理：设
p
p
p 为质数，则
C
n
k
≡
C
⌊
n
p
⌋
⌊
k
p
⌋
×
C
(
n
m
o
d
p
)
(
k
m
o
d
p
)
(
m
o
d
p
)
C_{n}^{k}≡ C_{\lfloor \frac{n}{p}\rfloor}^{\lfloor \frac{k}{p} \rfloor} \times C_{(n\,mod\,p)}^{(k\,mod\,p)}\, (mod\,p)
Cnk≡C⌊pn⌋⌊pk⌋×C(nmodp)(kmodp)(modp) 。
欧拉函数
φ
(
n
)
\varphi(n)
φ(n) 定义为
[
1
,
n
]
[1, n]
[1,n] 中与
n
n
n 互质的数的个数。
欧拉函数是积性函数：若
(
a
,
b
)
=
1
(a,b)=1
(a,b)=1 ，则
φ
(
a
b
)
=
φ
(
a
)
φ
(
b
)
\varphi(ab)=\varphi(a)\varphi(b)
φ(ab)=φ(a)φ(b) 。
-
若
n
=
p
k
，
p
为质数，则
φ
(
n
)
=
n
×
(
1
−
1
p
)
\color{red}{若 n=p^k，p 为质数，则 \varphi(n)=n\times (1-\frac{1}{p})}
若n=pk，p为质数，则φ(n)=n×(1−p1) 。
证明：若 ( x , p k ) > 1 (x, p^k)>1 (x,pk)>1，则有 p ∣ x p\,|\,x p∣x 成立， x x x 共有 ⌊ n p ⌋ \lfloor \frac{n}{p} \rfloor ⌊pn⌋个，因此 φ ( n ) = n − ⌊ n p ⌋ = n × ( 1 − 1 p ) \varphi(n)=n-\lfloor \frac{n}{p} \rfloor =n\times (1-\frac{1}{p}) φ(n)=n−⌊pn⌋=n×(1−p1) - 若 n 所有不同的质因子为 p 1 , p 2 , . . . , p k ，则 φ ( n ) = n ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) . . . ( 1 − 1 p k ) \color{red}{若 n 所有不同的质因子为 p_1,p_2,...,p_k，则 \varphi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})} 若n所有不同的质因子为p1,p2,...,pk，则φ(n)=n(1−p11)(1−p21)...(1−pk1) 。
[SDOI2012]Longge的问题
link
题意
求
∑
i
=
1
n
g
c
d
(
i
,
n
)
\sum\limits_{i=1}^{n} gcd(i,n)
i=1∑ngcd(i,n)，
n
≤
2
32
n≤2^{32}
n≤232 。
思路
注意到
g
c
d
(
i
,
n
)
gcd(i,n)
gcd(i,n) 一定是
n
n
n 的约数，
n
n
n 的约数不多于
n
\sqrt{n}
n 个。考虑枚举
n
n
n 的约数（设为
d
d
d ），再求出满足
g
c
d
(
i
,
n
)
=
d
gcd(i,n)=d
gcd(i,n)=d 的
i
i
i 有多少个。
显然不能是
n
d
\frac{n}{d}
dn，会算多。考虑将
g
c
d
(
i
,
n
)
=
d
gcd(i,n)=d
gcd(i,n)=d 转化成
g
c
d
(
i
d
,
n
d
)
=
1
gcd(\frac{i}{d},\frac{n}{d})=1
gcd(di,dn)=1。因为
1
≤
i
≤
n
1 \le i \le n
1≤i≤n，所以
1
≤
i
d
≤
n
d
1\le \frac{i}{d} \le \frac{n}{d}
1≤di≤dn 。个数就是求
[
1
,
n
d
]
[1,\frac{n}{d}]
[1,dn] 中与
n
d
\frac{n}{d}
dn 互质的个数，即
φ
(
n
d
)
\varphi(\frac{n}{d})
φ(dn) 。答案即为
∑
d
∣
n
d
×
φ
(
n
d
)
\sum\limits_{d|n} d\times \varphi(\frac{n}{d})
d∣n∑d×φ(dn) 。时间复杂度约为
O
(
n
0.5
)
O(n^{0.5})
O(n0.5) 。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int Get_phi(ll x){
ll phi=x;
for(ll i=2;i*i<=x;i++)
if(x%i==0){
while(x%i==0) x/=i;
phi/=i,phi*=(i-1);//不能写成 phi*=(i-1)/i !!
}
if(x>1) phi/=x,phi*=(x-1);
return phi;
}
int main(){
ll n; cin>>n;
ll ans=0;
for(ll i=1;i*i<=n;i++)
if(n%i==0){
ans+=Get_phi(n/i)*i;
if(n/i!=i) ans+=Get_phi(i)*(n/i);
}
cout<<ans;
return 0;
}
[Sdoi2008]沙拉公主的困惑
link
题意
回答
T
T
T 组询问：每组询问
[
1
,
n
!
]
[1, n!]
[1,n!] 中与
m
!
m!
m! 互质的数的个数，结果对
r
r
r 取模。
1
≤
m
≤
n
≤
1
0
7
，
1
≤
T
≤
1
0
4
，
2
≤
r
≤
1
0
9
+
10
且
r
为质数。
1≤m≤n≤10^7 ，1≤T≤10^4 ，2≤r≤10^9 +10 且 r 为质数。
1≤m≤n≤107，1≤T≤104，2≤r≤109+10且r为质数。
思路
因为有
g
c
d
(
i
,
m
!
)
=
g
c
d
(
m
!
×
k
+
i
,
m
!
)
gcd(i,m!)=gcd(m! \times k+i,m!)
gcd(i,m!)=gcd(m!×k+i,m!)，所以对于所有
∀
k
∈
[
1
,
n
!
m
!
]
,
[
(
k
−
1
)
×
M
!
+
1
,
k
×
M
!
]
∀k∈[1, \frac{n!}{m!}],[(k−1)×M!+1,k×M!]
∀k∈[1,m!n!],[(k−1)×M!+1,k×M!] 中与
m
!
m!
m! 互质的数是相等的。所以答案为
n
!
m
!
×
φ
(
m
!
)
\frac{n!}{m!} \times \varphi(m!)
m!n!×φ(m!)。
考虑如何求
a
n
s
=
n
!
m
!
×
φ
(
m
!
)
ans=\frac{n!}{m!} \times \varphi(m!)
ans=m!n!×φ(m!) 。
因为
φ
(
n
)
=
n
(
1
−
1
p
1
)
(
1
−
1
p
2
)
.
.
.
(
1
−
1
p
k
)
\varphi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})
φ(n)=n(1−p11)(1−p21)...(1−pk1)，将
m
!
m!
m! 代入得，
a
n
s
=
n
!
×
(
1
−
1
p
1
)
(
1
−
1
p
2
)
.
.
.
(
1
−
1
p
k
)
ans=n! \times(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})
ans=n!×(1−p11)(1−p21)...(1−pk1) （这里
p
1
.
.
.
p
k
p_1...p_k
p1...pk 为
m
!
m!
m! 的所有质因子，即不大于
m
m
m 的所有素数。)
化简得：
a
n
s
=
n
!
×
∏
(
p
i
−
1
)
∏
p
i
ans=n! \times \frac{\prod(p_i-1)}{\prod p_i}
ans=n!×∏pi∏(pi−1)。 线性求逆元、质数，预处理即可。注意模数
r
r
r 有可能小于
m
,
n
m,n
m,n，此时
n
!
n!
n! 和
1
∏
p
i
\frac{1}{\prod p_i}
∏pi1 中会消去一个
r
r
r 。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e7+5,N=1e7;
int prm[maxn],fac[maxn],g[maxn],inv[maxn],invp[maxn];//不要开太多 ll，会 MLE
bool isprm[maxn];
int main(){
int t,mod; cin>>t>>mod;
inv[1]=1;
for(ll i=2;i<=N;i++)
inv[i]=1ll*(-mod/i+mod)*inv[mod%i]%mod;
isprm[1]=fac[1]=g[1]=invp[1]=1;
int pn=0;
for(ll i=2;i<=N;i++){
fac[i]=(i!=mod?1ll*fac[i-1]*i%mod:fac[i-1]);
g[i]=g[i-1],invp[i]=invp[i-1];
if(!isprm[i]){
prm[++pn]=i;
g[i]=1ll*g[i]*(i-1)%mod;//注意 ll ，不能写成 (g[i]*=1ll*(i-1))%=mod ！！！
if(i!=mod) invp[i]=1ll*invp[i]*inv[i]%mod;
}
for(int j=1;j<=pn&&i*prm[j]<=N;j++){
isprm[i*prm[j]]=1;
if(i%prm[j]==0) break;
}
}
while(t--){
int n,m; cin>>n>>m;
if(n>=mod&&m<mod) cout<<"0\n";//若因子 mod 抵消不了，%mod 后就会为 0
else cout<<1ll*fac[n]*g[m]%mod*invp[m]%mod<<"\n";//！！！参考 https://www.luogu.com.cn/article/al267pxj
}
return 0;
}
欧拉定理
若 ( a , n ) = 1 (a,n)=1 (a,n)=1，则 a φ ( n ) ≡ 1 ( m o d n ) a^{\varphi(n)}≡1 \,(mod \,n) aφ(n)≡1(modn) 。
求逆元： a × a φ ( n ) − 1 ≡ 1 ( m o d n ) a\times a^{\varphi(n)-1} ≡1 \,(mod\, n) a×aφ(n)−1≡1(modn)；特别地，若 n n n 是质数 a × a n − 2 ≡ 1 ( m o d n ) a\times a^{n-2}≡1 \,(mod \,n) a×an−2≡1(modn) 。
欧拉定理的扩展
定理：
a
2
φ
(
n
)
≡
a
φ
(
n
)
(
m
o
d
n
)
a^{2\varphi(n)}≡a^{\varphi(n)}\, (mod \,n)
a2φ(n)≡aφ(n)(modn)
推论：当
b
≥
φ
(
n
)
b≥\varphi(n)
b≥φ(n) 时，
a
b
≡
a
(
b
m
o
d
φ
(
n
)
)
+
φ
(
n
)
(
m
o
d
n
)
a^b≡a^{(b \,mod \,\varphi(n)) + \varphi(n)}\, (mod \,n)
ab≡a(bmodφ(n))+φ(n)(modn)
LG P4139 上帝与集合的正确用法
link
题意
令
a
n
=
2
2
2
2
…
⏞
n
个
2
a_n=\overbrace{2^{2^{2^{2^{\dots}}}}}^{n 个 2}
an=2222…
n个2 ，求
lim
n
→
∞
(
a
n
m
o
d
m
)
\lim\limits_{n\rightarrow ∞}(a_n \,mod \, m)
n→∞lim(anmodm) 。
T
≤
1
0
3
,
p
≤
1
0
7
T≤10 ^3,p≤10^7
T≤103,p≤107
思路
题目说明了存在
lim
n
→
∞
(
a
n
m
o
d
m
)
\lim\limits_{n\rightarrow ∞}(a_n \,mod \, m)
n→∞lim(anmodm) 。
又因为有结论
2
a
n
≡
2
(
a
n
m
o
d
φ
(
m
)
)
+
φ
(
m
)
(
m
o
d
m
)
2^{a_n}≡2^{(a_n \,mod \,\varphi(m)) + \varphi(m)}\, (mod \,m)
2an≡2(anmodφ(m))+φ(m)(modm)，所以问题转化成求
lim
n
→
∞
(
a
n
m
o
d
φ
(
m
)
)
\lim\limits_{n\rightarrow ∞}(a_n \,mod \, \varphi(m))
n→∞lim(anmodφ(m)) 。
由于
φ
(
m
)
\varphi(m)
φ(m) 的
m
m
m 会越来越小，
m
=
1
m=1
m=1 时终止递归（开始回退），此时
φ
(
m
)
=
1
\varphi(m)=1
φ(m)=1 ，那么
(
a
n
m
o
d
1
)
=
0
(a_n mod 1)=0
(anmod1)=0 。
可以证明递归的层数不大于
2
l
o
g
2
m
2log_2m
2log2m ，总时间复杂度为
O
(
n
)
O(\sqrt{n})
O(n) 。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int Phi(int x){
int phi=x;
for(ll i=2;i*i<=x;i++)
if(x%i==0){
while(x%i==0) x/=i;
phi/=i,phi*=(i-1);
}
if(x>1) phi/=x,phi*=(x-1);
return phi;
}
int Pow_(ll x,ll y,ll mod){
ll s=1;
while(y){
if(y&1) (s*=x)%=mod;
(x*=x)%=mod;
y>>=1;
}
return s;
}
int Func(int m){
if(m==1) return 0;
int phi_m=Phi(m);
return Pow_(2,Func(phi_m)%phi_m+phi_m,m);
}
int main(){
int t; cin>>t;
while(t--){
int mod; cin>>mod;
cout<<Func(mod)<<"\n";
}
return 0;
}
线性筛与积性函数
Q
Q
Q：如何
O
(
n
)
O(n)
O(n) 求
[
1
,
n
]
[1,n]
[1,n] 的素数？
A
A
A：每个合数必须只被筛去一次，考虑
d
p
dp
dp 求
[
1
,
n
]
[1,n]
[1,n] 每个数的最小质因子，则每个合数在枚举到自己最小的质因子得时候被筛去即可。
积性函数：
f
(
1
)
=
1
f(1)=1
f(1)=1 。若
(
a
,
b
)
=
1
(a,b)=1
(a,b)=1, 则
f
(
a
b
)
=
f
(
a
)
f
(
b
)
f(ab)=f(a)f(b)
f(ab)=f(a)f(b) 。
常见的积性函数：
- φ ( n ) \varphi(n) φ(n)：欧拉函数
- d ( n ) d(n) d(n)：约数个数
- σ k ( n ) \sigma_k(n) σk(n)：约数的k次幂和
Q
Q
Q：给定积性函数
f
f
f，如何求
f
(
1
)
.
.
.
f
(
n
)
f(1)...f(n)
f(1)...f(n) 的值？
A
A
A：利用积性，设
n
=
p
k
n
′
n=p^kn'
n=pkn′（
p
p
p 是
n
n
n 最小的质因子，
k
k
k 是
p
p
p 在
n
n
n 中的次数）则有
f
(
n
)
=
f
(
p
k
)
f
(
n
′
)
f(n)=f(p^k)f(n')
f(n)=f(pk)f(n′) 。只需特别考虑
f
(
p
k
)
f(p^k)
f(pk)；其它用线性筛递推即可。
LG P2568 GCD
link
题意
给定正整数
n
n
n，求
1
≤
x
,
y
≤
n
1\le x,y\le n
1≤x,y≤n 且
gcd
(
x
,
y
)
\gcd(x,y)
gcd(x,y) 为素数的数对
(
x
,
y
)
(x,y)
(x,y) 有多少对。
1
≤
n
≤
1
0
7
1\le n\le10^7
1≤n≤107
思路
由题得，
g
c
d
(
x
,
y
)
=
d
gcd(x,y)=d
gcd(x,y)=d （
d
d
d 为质数）。令
x
′
=
x
d
,
y
′
=
y
d
x'=\frac{x}{d},y'=\frac{y}{d}
x′=dx,y′=dy，又有
g
c
d
(
x
′
,
y
′
)
=
1
gcd(x′,y′)=1
gcd(x′,y′)=1 。
- 若 x ′ ≥ y ′ x′ \ge y′ x′≥y′，有 φ ( x ′ ) \varphi(x′) φ(x′) 个 y ′ y′ y′ 满足 g c d ( x ′ , y ′ ) = 1 gcd(x′,y′)=1 gcd(x′,y′)=1；
- 若 x ′ ≤ y ′ x′ \le y′ x′≤y′，有 φ ( y ′ ) \varphi(y′) φ(y′) 个 x ′ x′ x′ 满足 g c d ( x ′ , y ′ ) = 1 gcd(x′,y′)=1 gcd(x′,y′)=1；
- 若 x ′ = y ′ x′ = y′ x′=y′，只有 1 1 1 种情况， x ′ = 1 , y ′ = 1 x′=1,y′=1 x′=1,y′=1；
所以对于任意 d d d，满足 g c d ( x , y ) = d gcd(x,y)=d gcd(x,y)=d 的个数有 ( 2 × ∑ i = 1 n d φ ( i ) ) − 1 (2\times \sum\limits_{i=1}^{\frac{n}{d}}\varphi(i))-1 (2×i=1∑dnφ(i))−1 个。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e7+5;
int prm[maxn],phi[maxn];
ll sum[maxn];
bool isprm[maxn];
int main(){
int n; cin>>n;
phi[1]=1;
int pn=0;
for(ll i=2;i<=n;i++){
if(!isprm[i]) prm[++pn]=i,phi[i]=i-1;
for(int j=1;j<=pn&&i*prm[j]<=n;j++){
int k=i*prm[j]; isprm[k]=1;
if(i%prm[j]==0){
phi[k]=phi[i]*prm[j];
break;
}
else phi[k]=phi[i]*phi[prm[j]];
}
}
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+phi[i];
ll ans=0;
for(int i=1;i<=pn;i++)
ans+=2*sum[n/prm[i]]-1;
cout<<ans;
return 0;
}
例题2
题意
求
∑
i
=
1
n
∑
j
=
1
n
(
−
1
)
d
(
i
j
)
\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} (-1)^{d(ij)}
i=1∑nj=1∑n(−1)d(ij)，
d
(
n
)
d(n)
d(n) 表示
n
n
n 的约数个数。
1
≤
n
≤
1
0
7
1\le n \le10^7
1≤n≤107
思路
由题目可知，若某个数的约数个数为奇数，取
−
1
-1
−1；否则取
1
1
1。
发现，只有完全平方数的约数个数才会为奇数。
\color{blue}{发现，只有完全平方数的约数个数才会为奇数。}
发现，只有完全平方数的约数个数才会为奇数。
考虑当为完全平方数时
i
,
j
i,j
i,j 有什么特点。设
i
=
a
×
b
2
i=a\times b^2
i=a×b2，其中
a
a
a 不能被大于
1
1
1 的完全平方数整除。设
f
(
i
)
=
a
f(i)=a
f(i)=a，则如果
i
×
j
i\times j
i×j 为完全平方数时，
f
(
i
)
=
f
(
j
)
f(i)=f(j)
f(i)=f(j)。
所以只需统计
f
(
1
)
…
f
(
n
)
f(1)\dots f(n)
f(1)…f(n) 中每种数的出现次数即可。
又发现，
f
(
)
f()
f() 为积性函数，特殊处理
f
(
p
k
)
=
p
k
m
o
d
2
f(p^k)=p^{k \,mod\,2}
f(pk)=pkmod2 ，用线性筛即可求出
f
(
)
f()
f() 。
补充题
[SDOI2009] SuperGCD
link
题意
给出两个整数
a
,
b
a,b
a,b，求
g
c
d
(
a
,
b
)
gcd(a,b)
gcd(a,b) 。
0
<
a
,
b
≤
1
0
10000
0\lt a,b\le 10^{10000}
0<a,b≤1010000
思路
如果直接用辗转相除法，就需要实现高精度除法，复杂度会有问题。
考虑按
奇偶
\color{purple}{奇偶}
奇偶 分类：
- 若 a , b a,b a,b 同为偶数，则 ( a , b ) = 2 × ( a 2 , b 2 ) (a,b)=2\times(\frac{a}{2},\frac{b}{2}) (a,b)=2×(2a,2b) ；
- 若 a , b a,b a,b 同为奇数，不妨设 a > b a>b a>b ，则 ( a , b ) = ( a − b 2 , b ) (a,b)=(\frac{a-b}{2},b) (a,b)=(2a−b,b) ；
- 若 a , b a,b a,b 一奇一偶，不妨设 a a a 为偶数，则 ( a , b ) = ( a 2 , b ) (a,b)=(\frac{a}{2},b) (a,b)=(2a,b) ；
只会经过
l
o
g
log
log 次迭代，每次操作只有
/
2
,
×
2
,
−
/ 2,\times2,-
/2,×2,−，用高精度即可。
注意卡常，递归会
m
l
e
mle
mle，建议改成递推。可以使用压位高精。
代码
卡常中……
[Violet 5] 樱花
link
题意
求
1
x
+
1
y
=
1
n
!
\frac{1}{x} +\frac{1}{y}=\frac{1}{n!}
x1+y1=n!1 的正整数解
(
x
,
y
)
(x,y)
(x,y) 的个数。
n
≤
1
0
6
n\le 10^6
n≤106，答案对
1
0
9
+
7
10^9+7
109+7 取模。
思路
设
z
=
n
!
z=n!
z=n! ，推一推式子就有
(
x
−
n
!
)
(
y
−
n
!
)
=
z
2
(x-n!)(y-n!)=z^2
(x−n!)(y−n!)=z2 ，即
a
=
x
−
n
!
,
b
=
y
−
n
!
a=x-n!,b=y-n!
a=x−n!,b=y−n!，原始又转化为
a
b
=
z
2
ab=z^2
ab=z2 。
若
a
,
b
a,b
a,b 为正整数，则
x
,
y
x,y
x,y 也一定为正整数。所以就是求
z
2
z^2
z2 的因数个数。
z
2
=
(
n
!
)
2
z^2=(n!)^2
z2=(n!)2，
(
n
!
)
2
(n!)^2
(n!)2 的质因数不大于
n
n
n。
由唯一分解定理得：
(
n
!
)
2
=
p
1
e
1
p
2
e
2
…
(n!)^2=p_{1}^{e_1}p_{2}^{e_2}\dots
(n!)2=p1e1p2e2… 。所以
(
n
!
)
2
(n!)^2
(n!)2 得因数个数为：
(
2
e
1
+
1
)
(
2
e
2
+
1
)
…
(2e_1+1)(2e_2+1)\dots
(2e1+1)(2e2+1)… 。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+5,mod=1e9+7;
int prm[maxn],gy[maxn];
ll f[maxn];
bool isprm[maxn];
int main(){
ll n; cin>>n;
int pn=0;
for(ll i=2;i<=n;i++){
if(!isprm[i]){
prm[++pn]=i;
gy[i]=i;//gy[i]：i 的最大质因子
}
for(int j=1;j<=pn&&i*prm[j]<=n;j++){
isprm[i*prm[j]]=1;
gy[i*prm[j]]=prm[j];//不能放在 if 的下面！！
if(i%prm[j]==0) break;
}
}
for(int i=1;i<=n;i++)
for(int j=i;j>1;j/=gy[j])
f[gy[j]]++,f[gy[j]]%=mod;
ll ans=1;
for(int i=1;i<=pn;i++)
(ans*=(f[prm[i]]*2+1))%=mod;//求 (n!)^2 的因子个数
cout<<ans;
return 0;
}
[CF 632D] Longest Subsequence
link
题意
给出
n
n
n 个数，要求选出尽可能多的数，满足它们的最小公倍数不大于
m
m
m 。
1
≤
n
,
m
≤
1
0
6
,
1
≤
a
i
≤
1
0
9
1≤n,m≤10^6, 1≤ai≤10^9
1≤n,m≤106,1≤ai≤109
思路
考虑枚举
l
c
m
lcm
lcm 。由于选出的数一定为
l
c
m
lcm
lcm 的约数，所以可以设
f
[
i
]
f[i]
f[i] 表示
i
i
i 的约数在
{
a
}
\{a\}
{a} 中有出现的个数。但是
f
[
]
f[]
f[] 不是积性函数，也就只能用埃氏筛求。时间复杂度约为
O
(
n
l
o
g
l
o
g
n
)
O(nloglogn)
O(nloglogn) 。
(
不知道怎么证明
?
)
\color{red}{(不知道怎么证明?)}
(不知道怎么证明?)
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int a[maxn],b[maxn],f[maxn],f2[maxn];
int main(){
int n2,m,n=0; cin>>n2>>m;
for(int i=1;i<=n2;i++){
cin>>b[i];
if(b[i]<=m){
if(!f2[b[i]]) a[++n]=b[i];
f2[b[i]]++;
}
}
/* 不能用线性筛！！！
因为 d[i] 表示 i 的约数个数时是积性函数，但是 f[i] 表示 i 的约数在 {a} 中有出现的个数，这并不是积性函数。
*/
for(int i=1;i<=n;i++)
for(int j=a[i];j<=m;j+=a[i])
f[j]+=f2[a[i]];
int ans=1;//此题中，空集的 lcm 等于 1 ！！
for(int i=2;i<=m;i++)
if(f[i]>f[ans]) ans=i;
cout<<ans<<" "<<f[ans]<<"\n";
for(int i=1;i<=n2;i++)
if(ans%b[i]==0) cout<<i<<" ";
return 0;
}
[CF 582A] GCD Table
link
题意
对一个长度为
n
n
n 的数列
a
a
a ，定义它的 GCD Table G 是一张
n
×
n
n×n
n×n 的二维表，其中
G
i
,
j
=
g
c
d
(
a
i
,
a
j
)
G_{i,j}=gcd(a_i, a_j)
Gi,j=gcd(ai,aj) 。现在乱序给出
G
G
G 中所有
n
2
n^2
n2 个数，求原数列
a
a
a 。
1
≤
n
≤
500
,
G
i
,
j
≤
1
0
9
1≤n≤500, G_{i,j}≤10^9
1≤n≤500,Gi,j≤109
思路
分析发现，
G
G
G 中最大的数一定也是
a
a
a 中最大的数，
G
G
G 中次大的数一定也是
a
a
a 中次大的数，第三、第四可能是由
a
a
a 中最大和次大的
g
c
d
gcd
gcd 产生的。但是对于已经确定的
{
a
}
\{a\}
{a} 我们可以先消掉他们之间的
g
c
d
gcd
gcd，剩下的
G
G
G 就变成了一个子问题，同样策略求解即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=505;
int a[maxn],g[maxn*maxn];
map<int,int>mp;
int main(){
int n; cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
int x; cin>>x;
g[(i-1)*n+j]=x,mp[x]++;
}
sort(g+1,g+n*n+1,[](int a,int b){ return a>b; });
for(int i=1,j=1;i<=n;i++){
while(!mp[g[j]]) j++;
a[i]=g[j],mp[g[j]]--;
for(int k=1;k<i;k++)
mp[__gcd(a[i],a[k])]-=2;
}
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
return 0;
}
[CF 687B] Remainders Game
link
题意
给定正整数
n
,
k
n,k
n,k 和
n
n
n 个正整数
c
1
,
c
2
,
…
,
c
n
c_1,c_2,\dots,c_n
c1,c2,…,cn 。如果对于任意正整数
x
x
x，可以通过
x
m
o
d
c
i
x\,mod\,c_i
xmodci 的值推出
x
m
o
d
k
x\,mod\,k
xmodk 的值则输出 Yes ，否则输出 No。
1
≤
n
,
k
,
c
i
≤
1
0
6
1\le n,k,c_i \le10^6
1≤n,k,ci≤106
思路
容易猜出结论：当且仅当
k
∣
l
c
m
(
c
1
,
c
2
,
.
.
.
,
c
n
)
k\,|\,lcm(c_1,c_2,...,c_n)
k∣lcm(c1,c2,...,cn) 时，输出 Yes；（证明参考扩展中国剩余定理
e
x
c
r
t
excrt
excrt）
方法一：将
k
,
l
c
m
k,lcm
k,lcm 都分解质因数，再比较两者质因数的次数；
方法二：在求
l
c
m
lcm
lcm 的时候加上取模，防止溢出。（这个比较好写）
可能要卡卡常。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll Get_gcd(ll a,ll b){ return !b?a:Get_gcd(b,a%b); }
ll Get_lcm(ll a,ll b){ return a*b/Get_gcd(a,b); }
inline int read(){
int x=0,f=1; char c=getchar();
while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); }
while(c>='0'&&c<='9'){ x=(x<<3)+(x<<1)+c-'0'; c=getchar(); }
return x*f;
}
int main(){
int n=read(),k=read(); ll d=1;
for(int i=1;i<=n;i++){
int c=read();
d=Get_lcm(d,c)%k;
}
cout<<(d%k==0?"Yes":"No");
return 0;
}
总结
简化题目，将其转化为式子（数）进行推导，得出性质。
![[QMT量化交易小白入门]-二十二、deepseek+cline+vscode,让小白使用miniQMT量化交易成为可能](https://i-blog.csdnimg.cn/direct/bc34fe33417c4de9a7be5957193242fe.png)
