前置知识
前言
本章节默认
n
=
∏
i
=
1
t
p
i
k
i
n=\prod_{i=1}^{t}p_i^{k_i}
n
=
∏
i
=
1
t
p
i
k
i
一、欧拉函数
1.
1.
1
.
通项公式
φ
(
n
)
=
∏
i
=
1
t
(
p
i
−
1
)
p
i
k
i
−
1
=
∏
i
=
1
t
(
1
−
1
p
i
)
p
i
k
i
=
n
∏
i
=
1
t
(
1
−
1
p
i
)
\varphi(n)=\prod_{i=1}^{t}(p_i-1)p_i^{k_i-1}=\prod_{i=1}^{t}(1-\frac{1}{pi})p_i^{k_i}=n\prod_{i=1}^{t}(1-\frac{1}{pi})
φ
(
n
)
=
i
=
1
∏
t
(
p
i
−
1
)
p
i
k
i
−
1
=
i
=
1
∏
t
(
1
−
p
i
1
)
p
i
k
i
=
n
i
=
1
∏
t
(
1
−
p
i
1
)
证明可以在百度百科中搜到，这里略过。
证明
2.
2.
2
.
欧拉定理降幂
欧拉定理
a
p
−
1
≡
1
(
m
o
d
p
)
p
为
质
数
a^{p-1}\equiv1(mod\space \space p)\qquad p为质数
a
p
−
1
≡
1
(
m
o
d
p
)
p
为
质
数
证明：
引理：
若
m
a
−
n
a
≡
0
(
m
o
d
p
)
且
g
c
d
(
a
,
p
)
=
1
，
则
(
m
−
n
)
为
p
的
倍
数
若ma-na \equiv 0(mod\space \space p)且gcd(a,p)=1，则(m-n)为p的倍数
若
m
a
−
n
a
≡
0
(
m
o
d
p
)
且
g
c
d
(
a
,
p
)
=
1
，
则
(
m
−
n
)
为
p
的
倍
数
那么
a
,
2
a
,
3
a
,
.
.
.
,
(
p
−
1
)
a
%
p
a,2a,3a,…,(p-1)a\%p
a
,
2
a
,
3
a
,
.
.
.
,
(
p
−
1
)
a
%
p
的余数必定各不相同，分别为
1
,
2
,
3
,
.
.
.
,
(
p
−
1
)
1,2,3,…,(p-1)
1
,
2
,
3
,
.
.
.
,
(
p
−
1
)
，(
a
a
a
不为
p
p
p
的倍数)
全部相乘，得
(
p
−
1
)
!
a
p
−
1
≡
(
p
−
1
)
!
(
m
o
d
p
)
(p-1)!a^{p-1}\equiv(p-1)!(mod\space\space p)
(
p
−
1
)
!
a
p
−
1
≡
(
p
−
1
)
!
(
m
o
d
p
)
a
p
−
1
≡
1
(
m
o
d
p
)
a^{p-1}\equiv1(mod\space \space p)
a
p
−
1
≡
1
(
m
o
d
p
)
广义欧拉定理
a
φ
(
p
)
≡
1
(
m
o
d
p
)
g
c
d
(
a
,
p
)
=
1
a^{\varphi(p)}\equiv1(mod\space \space p)\qquad gcd(a,p)=1
a
φ
(
p
)
≡
1
(
m
o
d
p
)
g
c
d
(
a
,
p
)
=
1
证明：
设
1
−
(
p
−
1
)
1-(p-1)
1
−
(
p
−
1
)
中与
p
p
p
互质的数为
x
1
,
x
2
,
.
.
.
,
x
n
x_1,x_2,…,x_n
x
1
,
x
2
,
.
.
.
,
x
n
，那么
x
1
a
,
x
2
a
,
.
.
.
,
x
n
a
%
p
x_1a,x_2a,…,x_na\%p
x
1
a
,
x
2
a
,
.
.
.
,
x
n
a
%
p
的余数也各不相同，且为
x
1
,
x
2
,
.
.
.
,
x
n
x_1,x_2,…,x_n
x
1
,
x
2
,
.
.
.
,
x
n
，证明方式与上面同理。
应用:在快速幂中指数过大，如求
a
b
c
%
p
(
p
为
质
数
)
a^{b^c}\%p\qquad(p为质数)
a
b
c
%
p
(
p
为
质
数
)
时
(
a
,
b
,
c
<
=
1
0
12
)
(a,b,c<=10^{12})
(
a
,
b
,
c
<
=
1
0
1
2
)
就可以
long long quickpow(long long a,long long b,long long Mod)
int main(){
int a,b,c,p;
scanf("%lld%lld%lld%lld",&a,&b,&c,&p);
printf("%lld\n",quickpow(a,quickpow(b,c,p-1),p);
}
3.
I
d
=
φ
∗
I
3.Id=\varphi*I
3
.
I
d
=
φ
∗
I
4.
φ
=
μ
∗
I
d
4.\varphi=\mu*Id
4
.
φ
=
μ
∗
I
d
3
,
4
3,4
3
,
4
的证明方法见
Dirichlet卷积初步
5.
∑
n
i
−
1
[
g
c
d
(
i
,
n
)
=
1
]
×
i
=
n
×
φ
(
n
)
+
[
n
=
1
]
2
5.\sum_{n}^{i-1}[gcd(i,n)=1]\times i=\frac{n\times\varphi(n)+[n=1]}{2}
5
.
∑
n
i
−
1
[
g
c
d
(
i
,
n
)
=
1
]
×
i
=
2
n
×
φ
(
n
)
+
[
n
=
1
]
证明：当
n
=
1
n=1
n
=
1
时，易证等式成立
当
n
≠
1
n\not =1
n
=
1
时，因为
g
c
d
(
i
,
n
)
=
g
c
d
(
n
−
i
,
n
)
gcd(i,n)=gcd(n-i,n)
g
c
d
(
i
,
n
)
=
g
c
d
(
n
−
i
,
n
)
，所以所有的
i
i
i
必成对出现，一共有
φ
(
n
)
2
对
\frac{\varphi(n)}{2}对
2
φ
(
n
)
对
，所以和为
n
×
φ
(
n
)
2
\frac{n\times\varphi(n)}{2}
2
n
×
φ
(
n
)
6.
φ
(
i
j
)
=
φ
(
i
)
φ
(
j
)
g
c
d
(
i
,
j
)
φ
(
g
c
d
(
i
,
j
)
)
6.\varphi(ij)=\frac{\varphi(i)\varphi(j)gcd(i,j)}{\varphi(gcd(i,j))}
6
.
φ
(
i
j
)
=
φ
(
g
c
d
(
i
,
j
)
)
φ
(
i
)
φ
(
j
)
g
c
d
(
i
,
j
)
证明：由于
φ
\varphi
φ
为积性函数，所以我们只需证明满足质数的整数次幂的情况。
当
i
=
1
或
j
=
1
i=1或j=1
i
=
1
或
j
=
1
时显然成立。
设
i
=
p
s
,
j
=
p
t
i=p^s,j=p^t
i
=
p
s
,
j
=
p
t
，则
φ
(
i
)
φ
(
j
)
g
c
d
(
i
,
j
)
φ
(
g
c
d
(
i
,
j
)
)
\frac{\varphi(i)\varphi(j)gcd(i,j)}{\varphi(gcd(i,j))}
φ
(
g
c
d
(
i
,
j
)
)
φ
(
i
)
φ
(
j
)
g
c
d
(
i
,
j
)
=
(
p
−
1
)
2
p
s
+
t
+
m
i
n
(
s
,
t
)
−
2
(
p
−
1
)
p
m
i
n
(
s
,
t
)
−
1
=\frac{(p-1)^2p^{s+t+min(s,t)-2}}{(p-1)p^{min(s,t)-1}}
=
(
p
−
1
)
p
m
i
n
(
s
,
t
)
−
1
(
p
−
1
)
2
p
s
+
t
+
m
i
n
(
s
,
t
)
−
2
=
(
p
−
1
)
p
s
+
t
−
1
=(p-1)p^{s+t-1}
=
(
p
−
1
)
p
s
+
t
−
1
=
φ
(
p
s
+
t
)
=
φ
(
i
j
)
=\varphi(p^{s+t})=\varphi(ij)
=
φ
(
p
s
+
t
)
=
φ
(
i
j
)
二、莫比乌斯函数
首先，要明白它的定义式：
对于一个数n,
{
∑
d
∣
n
μ
(
d
)
}
=
[
n
=
1
]
\{\sum_{d|n}\mu(d)\}=[n=1]
{
∑
d
∣
n
μ
(
d
)
}
=
[
n
=
1
]
当
n
n
n
不等于
1
1
1
时，
n
n
n
所有因子的莫比乌斯函数值的
和
和
和
为
0
0
0
。
易得，
μ
(
1
)
=
1
\mu(1)=1
μ
(
1
)
=
1
，取
n
=
p
k
n=p^k
n
=
p
k
（
p
p
p
为质数，
k
>
1
k>1
k
>
1
），由定义式可得：
μ
(
n
)
=
μ
(
1
)
+
μ
(
p
)
+
μ
(
p
2
)
+
.
.
.
+
μ
(
p
k
−
1
)
=
0
\mu(n)=\mu(1)+\mu(p)+\mu(p^2)+…+\mu(p^{k-1})=0
μ
(
n
)
=
μ
(
1
)
+
μ
(
p
)
+
μ
(
p
2
)
+
.
.
.
+
μ
(
p
k
−
1
)
=
0
取
k
=
2
k=2
k
=
2
，得
μ
(
p
)
=
−
1
\mu(p)=-1
μ
(
p
)
=
−
1
然后可以进一步推出对于
∀
k
≥
2
，
μ
(
p
k
)
=
0
∀k≥2，\mu(p^k)=0
∀
k
≥
2
，
μ
(
p
k
)
=
0
然后我们就得到了一个结论：当
n
n
n
的一个质因子的次数大于等于
2
2
2
时，
μ
(
n
)
=
0
\mu(n)=0
μ
(
n
)
=
0
由于
μ
\mu
μ
函数为积性函数，所以
μ
(
i
j
)
=
μ
(
i
)
μ
(
j
)
\mu(ij)=\mu(i)\mu(j)
μ
(
i
j
)
=
μ
(
i
)
μ
(
j
)
当
n
n
n
不存在一个质因子的次数大于
2
2
2
时，我们设
n
=
∏
i
=
1
t
p
i
n=\prod_{i=1}^{t}p_i
n
=
∏
i
=
1
t
p
i
∴
μ
(
n
)
=
μ
(
p
1
)
×
μ
(
p
2
)
×
.
.
.
×
μ
(
p
t
)
=
(
−
1
)
t
\therefore \qquad \mu(n)=\mu(p_1)\times\mu(p_2)\times…\times\mu(p_t)=(-1)^t
∴
μ
(
n
)
=
μ
(
p
1
)
×
μ
(
p
2
)
×
.
.
.
×
μ
(
p
t
)
=
(
−
1
)
t
综上所述
μ
(
n
)
=
{
0
n
有
平
方
因
子
(
−
1
)
t
o
t
h
e
r
w
i
s
e
\mu(n)=\left\{ \begin{aligned} 0\qquad n有平方因子 \\ (-1)^t \qquad otherwise\\ \end{aligned} \right.
μ
(
n
)
=
{
0
n
有
平
方
因
子
(
−
1
)
t
o
t
h
e
r
w
i
s
e
void sieve(){ //莫比乌斯函数筛法
mu[1]=1;
for(int i=2;i<=n;i++){
if(!flag[i]) prime[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
flag[i*prime[j]]=1;
if(i%prime[j]==0) break;
mu[i*prime[j]]-=mu[i];
}
}
}
三、约数个数函数
一个重要的性质
d
(
i
j
)
=
∑
k
∣
i
∑
l
∣
j
[
g
c
d
(
k
,
l
)
=
1
]
d(ij)=\sum_{k|i}\sum_{l|j}[gcd(k,l)=1]
d
(
i
j
)
=
k
∣
i
∑
l
∣
j
∑
[
g
c
d
(
k
,
l
)
=
1
]
证明：
设
q
q
q
为
i
j
ij
i
j
的一个因子(可以是质因子)，设
q
=
s
×
p
t
q=s\times p^t
q
=
s
×
p
t
（
p
p
p
为质数）
设
i
=
i
′
×
p
a
,
j
=
j
′
×
p
b
i=i’\times p^a,j=j’\times p^b
i
=
i
′
×
p
a
,
j
=
j
′
×
p
b
，由于
q
q
q
为
i
j
ij
i
j
的一个因子，必有
t
≤
a
+
b
t≤a+b
t
≤
a
+
b
如果
t
≤
a
t≤a
t
≤
a
，就取
k
=
m
×
p
t
k=m\times p^t
k
=
m
×
p
t
以保证
g
c
d
(
k
,
l
)
=
1
gcd(k,l)=1
g
c
d
(
k
,
l
)
=
1
否则取
k
k
k
满足
g
c
d
(
k
,
p
)
=
1
gcd(k,p)=1
g
c
d
(
k
,
p
)
=
1
，
t
=
n
×
p
t
−
a
t=n\times p^{t-a}
t
=
n
×
p
t
−
a
，此时
g
c
d
(
k
,
l
)
=
1
gcd(k,l)=1
g
c
d
(
k
,
l
)
=
1
。
这样可以保证对于
i
j
ij
i
j
的每一个约数都存在唯一一种分解方案，该性质成立。