这部分内容介绍了欧拉函数,积性函数
计数问题初步,以及同余初步

互质与欧拉函数

euler01

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

Euler函数的性质与积性函数

Euler函数性质

gcd(n,x)=gcd(n,nx)\textbf{gcd}(n,x) = \textbf{gcd}(n, n-x)
所以1n1\to n 的数中,与nn 不互质的数的平均值为

(ii+(ni)2)/k=n/2\left(\sum_i \frac{i+(n-i)}{2} \right)/ k = n/2

nn 互质的数的平均值也为n/2n/2

性质1
n>1,[1,n]\forall n > 1, [1, n] 中与nn 互质的数的和为n2ϕ(n)\frac{n}{2} \cdot \phi(n)

性质2:积性函数
gcd(a,b)=1,ϕ(ab)=ϕ(a)ϕ(b)\text{gcd}(a, b)=1, \phi(ab) = \phi(a) \phi(b)

Euler函数的积性

euler02
euler03
euler04

注意到,其中f(nm)=f(n)f(m)f(nm) = f(n) \cdot f(m)
中间的一步是根据乘法原理
d(nm)=(dn)(dm)d \mid (nm) = (d \mid n) \cup (d \mid m)
nmnm中有多少个满足条件的约数dd
实际上等于 满足条件的d1nd_1 \mid n个数乘上 满足条件的d2nd_2 \mid n 的个数

POJ3090
POJ3090

实际上,这个问题,除了(1,0),(0,1),(1,1)(1,0), (0, 1), (1, 1)
这三个点之外,(x,y)(x, y) 满足条件,当且仅当
1x,yN,xy1 \leqslant x,y \leqslant N, x \neq y 并且gcd(x,y)=1\text{gcd}(x, y)=1

根据对称性,实际上,对于2yN2 \leqslant y \leqslant N
找到对应的1x<y1 \leqslant x < y 并且gcd(x,y)=1\text{gcd}(x, y)=1
这样的ϕ(y)\phi (y) 就是答案

ans=3+2i=2Nϕ(i)\textbf{ans} = 3 + 2\cdot \sum_{i = 2}^{N} \phi(i)

Eratosthenes筛求Euler函数
一开始用ϕ(i)=i\phi(i) = i 表示ii 是一个质数
然后更新j=[i,2i,3i,,N]j = [i, 2i, 3i, \cdots, N]ii 作为一个素因子

ϕ(j)=ϕ(j)i1i\phi(j) = \phi(j) * \frac{i-1}{i}

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

const int maxn = 1000 + 10;
int phi[maxn];
int N;

void euler(int N) {
_rep(i, 2, N) phi[i] = i;
_rep(i, 2, N) {
if(phi[i] == i) {
for(int j = i; j <= N; j += i) phi[j] = phi[j] / i * (i-1);
}
}
}

void init() {
memset(phi, 0, sizeof(phi));
}

int main() {
freopen("input.txt", "r", stdin);
int kase;
cin >> kase;

int T = 0;
while (kase--) {
init();
scanf("%d", &N);

// then solve
euler(N);
int sum = 0;
_rep(i, 2, N) sum += phi[i];
sum *= 2, sum += 3;

printf("%d %d %d\n", ++T, N, sum);
}
}

线性筛法递推求Euler函数

线性筛法的思路是,每个合数仅仅被最小质因子pp 筛一次
fl[]fl[\cdots] 标记最小质因子

i,fl[i]=0,i\forall i, fl[i] = 0, i 为素数,储存到prime\to prime
i=[2,N]\forall i = [2, N] , 为当前的ii
乘上一个当前已得到的素因子xprime\forall x \in prime

i×xfl[...]{fl[i]xi \times x \xrightarrow{fl[...]} \begin{cases} fl[i] \\ x \end{cases}

更新fl[ix]fl[i \cdot x],即ixi \cdot x 的最小素因子
它要么是fl[i]fl[i],要么是xx
if fl[i]<x\textbf{if} \ fl[i] < x 当前素因子就已经被找到了,不检查其他primeprime
else, fl[ix]=x\textbf{else}, \ fl[i \cdot x] = x

那么Euler其实就是在上述算法的基础上
每一次标记最小素因子,并且只在第一次标记的时候,记录

ϕ(ip)={ϕ(i)ppiϕ(i)(p1)pi\phi(i \cdot p) = \begin{cases} \phi(i) \cdot p && p \mid i \\ \phi(i) \cdot (p-1) && p \nmid i \end{cases}

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
const int maxn = 1000 + 10;
int phi[maxn], fl[maxn];
int N;

void euler(int N, vector<int>& prime) {
memset(fl, 0, sizeof(fl));
prime.clear();

_rep(i, 2, N) {
if(fl[i] == 0) {
fl[i] = i, prime.push_back(i);
phi[i] = i - 1;
}
for(const auto& x : prime) {
if(fl[i] < x || i * x > N) break;
fl[i*x] = x;
phi[i*x] = phi[i] * (i % x ? x - 1 : x);
}
}
}

int main() {
freopen("input.txt", "r", stdin);
int kase;
cin >> kase;
int T = 0;
while (kase--) {
scanf("%d", &N);
vector<int> prime;
euler(N, prime);

int sum = 0;
_rep(i, 2, N) sum += phi[i];
sum *= 2, sum += 3;

printf("%d %d %d\n", ++T, N, sum);
}
}

积性函数与Dirichlet卷积

f(n)f(n) 满足f(1)=1,x,yN+f(1)=1, \quad \forall x, y \in \mathbb{N_{+}}
对于gcd(x,y)=1\textbf{gcd}(x,y)=1,均有f(xy)=f(x)f(y)f(xy)=f(x)f(y),f(n)f(n)积性函数

f(n)f(n) 对任意的x,yN+\forall x, y \in \mathbb{N_{+}},不必要求互质,均有f(xy)=f(x)f(y)f(xy)=f(x)f(y),f(n)f(n)完全积性函数

常见的积性函数

单位函数

ϵ(n)={1n=10otherwise\epsilon(n) = \begin{cases} 1 && n = 1 \\ 0 && \text{otherwise} \end{cases}

幂函数
Idk(n)=nk\textbf{Id}_k(n) = n^k 完全积性
k=1,Id(n)=nk=1, \textbf{Id}(n) = n,是恒等函数,自身映射到自身
k=0,1(n)k=0, \textbf{1}(n) 为常数函数,恒为11

除数函数

σk(n)=dndk\sigma_k(n) = \sum_{d \mid n} d^k

k=1,σ(n)=dndk = 1, \sigma(n) = \sum_{d \mid n} d 为因素和函数
k=0,σ0(n)=dnk = 0, \sigma_0(n) = \sum_{d \mid n} nn 的因素的个数

莫比乌斯函数

μ(n)={1n=10n含有平方因子,d>1,d2n(1)kk 为 n 的本质不同质因子的个数\mu(n) = \begin{cases} 1 && n = 1 \\ 0 && n \textbf{含有平方因子}, \exists d > 1, d^2 | n \\ (-1)^{k} && k \text{ 为 } n \ \textbf{的本质不同质因子的个数} \end{cases}

详细解释如下
n=i=1kpicin = \prod_{i = 1}^{k} p_i^{c_i}

  • n1n \neq 1
    • 存在i[1,k],ci>1,μ(n)=0i \in [1, k], c_i > 1, \mu(n)=0
      只要有某个质因子出现的次数>1,μ(n)=0>1, \mu(n)=0
    • 当任意的i[1,k]i \in [1, k],均有ci=1c_i = 1时,μ(n)=(1)k\mu(n) = (-1)^k
      每个质因子都仅仅只出现过一次时,n=i=1kpin = \prod_{i=1}^{k} p_i,也就是说
      n=p1p2pmn = p_1p_2 \cdots p_m, 唯一分解之后,每个因子都只出现一次
      kk 等于仅仅只出现一次的质因子的总个数,μ(n)=(1)k\mu(n) = (-1)^k

Dirichlet函数

(fg)(n)=dnf(d)g(nd)(f * g)(n) = \sum_{d \mid n} f(d)g(\frac{n}{d})

其中f,gf, g 为数论函数,一般来说具有积性
下图给出 Dirichlet 函数积性的证明

dirichlet

数论函数之间的关系

利用 dirichlet卷积,可以得到一些数论函数的关系

除数函数与幂函数

(f1)(n)=dnf(n)1(nd)=dnf(n)(f*\textbf{1})(n) = \sum_{d\mid n}f(n)\textbf{1}(\frac{n}{d}) = \sum_{d\mid n} f(n)

所以有

(Idk1)(n)=dnIdk(d)=dndkIdk1=σk(\textbf{Id}_{k}*\textbf{1})(n)= \sum_{d\mid n} \text{Id}_{k}(d) = \sum_{d\mid n} d^k \Longrightarrow \textbf{Id}_{k} * \textbf{1} = \sigma_k

Euler函数与恒等函数

(ϕ1)(n)=dnϕ(d)(\phi * \textbf{1})(n) = \sum_{d \mid n} \phi(d)

之前证明过rhs=n\textbf{rhs} = n

ϕ1=Id\phi * \textbf{1} = \text{Id}

数论函数之间的关系

ϵ=μ1ϵ(n)=dnμ(d)1(nd)=dnμ(d)\epsilon = \mu * \textbf{1} \Longrightarrow \epsilon(n) = \sum_{d \mid n} \mu (d)\textbf{1}(\frac{n}{d}) = \sum_{d \mid n} \mu (d)

dirichlet卷积性质

  • 交换律

    • fg=gff * g = g * f
    • proof

      (fg)(n)=xy=nf(x)g(y)xyxy=ng(x)f(y)=(gf)(n)(f * g)(n)= \sum_{xy=n}f(x)g(y) \xrightarrow{x \leftrightarrow y} \sum_{xy=n} g(x)f(y) = (g * f)(n)

  • 结合律

    • (fg)h=f(gh)(f * g) * h = f * (g * h)
    • proof

      ((fg)h)(n)=xy=n(fg)(x)h(y)=xy=n(uv=xf(u)g(v))h(y)=xy=n(uv=xf(u)g(v)h(y))\begin{gathered} \left( (f*g) * h \right)(n) = \sum_{xy=n} (f*g)(x) \cdot h(y) = \\ \sum_{xy = n} \left(\sum_{uv = x}f(u)g(v) \right) \cdot h(y) = \sum_{xy=n} \left( \sum_{uv=x} f(u)g(v)h(y) \right) \end{gathered}

      注意到uvy=nuvy=n,根据对称性

      rhs=uvy=nf(u)g(v)h(y)ux,vu,yvxuv=nf(x)g(u)h(v)\textbf{rhs}=\sum_{uvy=n}f(u)g(v)h(y) \xrightarrow{u \leftrightarrow x, v \leftrightarrow u, y \leftrightarrow v} \sum_{xuv=n}f(x)g(u)h(v)

      let uv=y\textbf{let} \ uv = y

      xy=n(uv=yf(x)g(u)h(v))=xy=n(f(x)uv=yg(u)h(v))=xy=nf(x)(gh)(y)=(f(gh))(n)\begin{gathered} \sum_{xy=n}\left( \sum_{uv=y}f(x)g(u)h(v)\right)= \sum_{xy=n} \left(f(x) \cdot \sum_{uv=y}g(u)h(v) \right) = \\ \sum_{xy=n} f(x) \cdot (g * h)(y) = (f * (g * h))(n) \end{gathered}

  • 函数加法分配律

    • f(g+h)=fg+fhf * (g+h) = f * g + f * h
    • proof

      (f(g+h))(n)=xy=nf(x)(g+h)(y)=xy=n(f(x)g(y)+f(x)h(y))=xy=nf(x)g(y)+xy=nf(x)h(y)=(fg)(n)+(fh)(n)\begin{gathered} (f * (g+h))(n) = \sum_{xy=n} f(x)(g+h)(y) = \sum_{xy=n} \left(f(x)g(y) + f(x)h(y) \right) = \\ \sum_{xy=n}f(x)g(y) + \sum_{xy=n} f(x)h(y) = (f*g)(n) + (f*h)(n) \end{gathered}

  • 单位元ϵ\epsilon

    • proof

      (ϵf)(n)=dnϵ(d)f(nd)d=1,ϵ0=f(n)(\epsilon * f)(n) = \sum_{d \mid n} \epsilon(d) f(\frac{n}{d}) \xrightarrow{d = 1, \epsilon \neq 0} = f(n)

  • 逆元

    • 假设fg=ϵf * g = \epsilon,那么ggff 的逆元

    • 逆元的求解

      (ff1)(1)=d1f(d)f1(1d)=f(1)f1(1)=1f1=1f(1)(f * f^{-1})(1) = \sum_{d \mid 1} f(d)f^{-1}(\frac{1}{d}) = f(1)f^{-1}(1) = 1 \rightarrow f^{-1} = \frac{1}{f(1)}

      所以必要条件是f(1)0f(1) \neq 0

      ϵ(2)=0=(ff1)(2)=d2f(d)f1(2d)=f(1)f1(2)+f(2)f1(1)f1(2)=f(2)f1(1)f(1)\begin{gathered} \epsilon(2) = 0 = (f * f^{-1})(2) = \sum_{d \mid 2} f(d)f^{-1}(\frac{2}{d}) = f(1)f^{-1}(2) + f(2)f^{-1}(1) \\ f^{-1}(2) = - \frac{f(2)f^{-1}(1)}{f(1)} \end{gathered}

    • 同理可推出逆元的表达式

      g(n)={1f(n)n=11f(1)dn,d>1f(d)g(nd)otherwiseg(n) = \begin{cases} \frac{1}{f(n)} && n = 1 \\ -\frac{1}{f(1)} \sum_{d \mid n, d > 1}f(d)g(\frac{n}{d}) && \text{otherwise} \end{cases}

    • proof

      • n=1,(fg)(n)=d1f(d)g(1d)=f(1)g(1)=1n = 1, (f * g)(n) = \sum_{d \mid 1} f(d)g(\frac{1}{d}) = f(1)g(1) = 1
      • n>1n > 1

        (fg)(n)=dnf(d)g(nd)=f(1)g(n)+dn,d>1f(d)g(nd)=f(1)f(1)dn,d>1f(d)g(nd)+dn,d>1f(d)g(nd)=0\begin{gathered} (f * g)(n) = \sum_{d \mid n} f(d)g\left(\frac{n}{d} \right) = f(1)g(n) + \sum_{d\mid n, d > 1}f(d)g\left( \frac{n}{d} \right) \\ = -\frac{f(1)}{f(1)} \sum_{d \mid n, d > 1} f(d)g\left( \frac{n}{d} \right) + \sum_{d \mid n, d > 1} f(d)g \left(\frac{n}{d} \right) = 0 \end{gathered}

    • 积性函数必然存在逆元,且逆元仍是积性函数,因为f(1)=10f(1) = 1 \neq 0

      • 根据表达式

      f1(n)={1f(n)n=11f(1)dn,d>1f(d)f1(nd)otherwisef^{-1}(n) = \begin{cases} \frac{1}{f(n)} && n = 1 \\ -\frac{1}{f(1)} \sum_{d \mid n, d > 1}f(d)f^{-1}(\frac{n}{d}) && \text{otherwise} \end{cases}

      f1(1)=1f^{-1}(1)=1,则对任意的正整数aaf1(a)f1(1)=f1(a)=f1(a1)f^{-1}(a)f^{-1}(1) = f^{-1}(a) = f^{-1}(a \cdot 1)

      • proof
        dirichlet02
        dirichlet03