前置知识

Dirichlet卷积初步

前言

本章节默认

n

=

∏

i

=

1

t

p

i

k

i

n=\prod_{i=1}^{t}p_i^{k_i}

n=∏i=1t​piki​​

一、欧拉函数

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​(pi​−1)piki​−1​=i=1∏t​(1−pi1​)piki​​=ni=1∏t​(1−pi1​)
证明可以在百度百科中搜到，这里略过。证明

2.

2.

2.欧拉定理降幂

欧拉定理

a

p

−

1

≡

1

(

m

o

d

  

p

)

p

为

质

数

a^{p-1}\equiv1(mod\space \space p)\qquad p为质数

ap−1≡1(mod  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的倍数

若ma−na≡0(mod  p)且gcd(a,p)=1，则(m−n)为p的倍数

那么

a

,

2

a

,

3

a

,

.

.

.

,

(

p

−

1

)

a

%

p

a,2a,3a,…,(p-1)a\%p

a,2a,3a,...,(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)!ap−1≡(p−1)!(mod  p)

a

p

−

1

≡

1

(

m

o

d

  

p

)

a^{p-1}\equiv1(mod\space \space p)

ap−1≡1(mod  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(mod  p)gcd(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

x1​,x2​,...,xn​，那么

x

1

a

,

x

2

a

,

.

.

.

,

x

n

a

%

p

x_1a,x_2a,…,x_na\%p

x1​a,x2​a,...,xn​a%p的余数也各不相同，且为

x

1

,

x

2

,

.

.

.

,

x

n

x_1,x_2,…,x_n

x1​,x2​,...,xn​，证明方式与上面同理。

应用:在快速幂中指数过大，如求

a

b

c

%

p

(

p

为

质

数

)

a^{b^c}\%p\qquad(p为质数)

abc%p(p为质数)时

(

a

,

b

,

c

<

=

1

0

12

)

(a,b,c<=10^{12})

(a,b,c<=1012)就可以

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.Id=φ∗I

4.

φ

=

μ

∗

I

d

4.\varphi=\mu*Id

4.φ=μ∗Id

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.∑ni−1​[gcd(i,n)=1]×i=2n×φ(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)

gcd(i,n)=gcd(n−i,n)，所以所有的

i

i

i必成对出现，一共有

φ

(

n

)

2

对

\frac{\varphi(n)}{2}对

2φ(n)​对，所以和为

n

×

φ

(

n

)

2

\frac{n\times\varphi(n)}{2}

2n×φ(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.φ(ij)=φ(gcd(i,j))φ(i)φ(j)gcd(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=ps,j=pt，则

φ

(

i

)

φ

(

j

)

g

c

d

(

i

,

j

)

φ

(

g

c

d

(

i

,

j

)

)

\frac{\varphi(i)\varphi(j)gcd(i,j)}{\varphi(gcd(i,j))}

φ(gcd(i,j))φ(i)φ(j)gcd(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)pmin(s,t)−1(p−1)2ps+t+min(s,t)−2​

=

(

p

−

1

)

p

s

+

t

−

1

=(p-1)p^{s+t-1}

=(p−1)ps+t−1

=

φ

(

p

s

+

t

)

=

φ

(

i

j

)

=\varphi(p^{s+t})=\varphi(ij)

=φ(ps+t)=φ(ij)

二、莫比乌斯函数

首先，要明白它的定义式：

对于一个数n,

{

∑

d

∣

n

μ

(

d

)

}

=

[

n

=

1

]

\{\sum_{d|n}\mu(d)\}=[n=1]

{∑d∣n​μ(d)}=[n=1]

当$n$不等于$1$时，$n$所有因子的莫比乌斯函数值的$和$为$0$。

易得，

μ

(

1

)

=

1

\mu(1)=1

μ(1)=1，取

n

=

p

k

n=p^k

n=pk（

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)+μ(p2)+...+μ(pk−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，μ(pk)=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)

μ(ij)=μ(i)μ(j)

当

n

n

n不存在一个质因子的次数大于

2

2

2时，我们设

n

=

∏

i

=

1

t

p

i

n=\prod_{i=1}^{t}p_i

n=∏i=1t​pi​

∴

μ

(

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)=μ(p1​)×μ(p2​)×...×μ(pt​)=(−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)={0n有平方因子(−1)totherwise​

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(ij)=k∣i∑​l∣j∑​[gcd(k,l)=1]
证明：

设

q

q

q为

i

j

ij

ij的一个因子(可以是质因子)，设

q

=

s

×

p

t

q=s\times p^t

q=s×pt（

p

p

p为质数）

设

i

=

i

′

×

p

a

,

j

=

j

′

×

p

b

i=i’\times p^a,j=j’\times p^b

i=i′×pa,j=j′×pb，由于

q

q

q为

i

j

ij

ij的一个因子，必有

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×pt以保证

g

c

d

(

k

,

l

)

=

1

gcd(k,l)=1

gcd(k,l)=1

否则取

k

k

k满足

g

c

d

(

k

,

p

)

=

1

gcd(k,p)=1

gcd(k,p)=1，

t

=

n

×

p

t

−

a

t=n\times p^{t-a}

t=n×pt−a，此时

g

c

d

(

k

,

l

)

=

1

gcd(k,l)=1

gcd(k,l)=1。

这样可以保证对于

i

j

ij

ij的每一个约数都存在唯一一种分解方案，该性质成立。