数学问题（三）

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

互质与欧拉函数

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函数性质

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

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

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

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

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

Euler函数的积性

注意到，其中 $f(nm) = f(n) \cdot f(m)$
中间的一步是根据乘法原理
$d \mid (nm) = (d \mid n) \cup (d \mid m)$
$nm$中有多少个满足条件的约数 $d$
实际上等于 满足条件的 $d_1 \mid n$ 的个数乘上 满足条件的 $d_2 \mid n$ 的个数

POJ3090

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

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

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

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

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

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函数

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

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

$$i \times x \xrightarrow{fl[...]} \begin{cases} fl[i] \\ x \end{cases}$$

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

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

$$\phi(i \cdot p) = \begin{cases} \phi(i) \cdot p && p \mid i \\ \phi(i) \cdot (p-1) && p \nmid i \end{cases}$$

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(1)=1, \quad \forall x, y \in \mathbb{N_{+}}$
对于 $\textbf{gcd}(x,y)=1$，均有 $f(xy)=f(x)f(y)$, $f(n)$ 为积性函数

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

常见的积性函数

单位函数

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

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

除数函数

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

$k = 1, \sigma(n) = \sum_{d \mid n} d$ 为因素和函数
$k = 0, \sigma_0(n) = \sum_{d \mid n}$ 为 $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 = \prod_{i = 1}^{k} p_i^{c_i}$

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

Dirichlet函数

$$(f * g)(n) = \sum_{d \mid n} f(d)g(\frac{n}{d})$$

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

数论函数之间的关系

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

除数函数与幂函数

$$(f*\textbf{1})(n) = \sum_{d\mid n}f(n)\textbf{1}(\frac{n}{d}) = \sum_{d\mid n} f(n)$$

所以有

$$(\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函数与恒等函数

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

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

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

数论函数之间的关系

$$\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卷积性质

• 交换律

  • $f * g = g * f$
  • proof

    $$(f * g)(n)= \sum_{xy=n}f(x)g(y) \xrightarrow{x \leftrightarrow y} \sum_{xy=n} g(x)f(y) = (g * f)(n)$$

• 结合律

  • $(f * g) * h = f * (g * h)$
  • proof

    $$\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=n$，根据对称性

    $$\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)$$

    $\textbf{let} \ uv = y$

    $$\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) = f * g + f * h$
  • proof

    $$\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

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

• 逆元

  • 假设 $f * g = \epsilon$，那么 $g$ 是 $f$ 的逆元

  • 逆元的求解

    $$(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) \neq 0$

    $$\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) = \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, (f * g)(n) = \sum_{d \mid 1} f(d)g(\frac{1}{d}) = f(1)g(1) = 1$
    • $n > 1$

      $$\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) = 1 \neq 0$

    • 根据表达式

    $$f^{-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}$$

    $f^{-1}(1)=1$，则对任意的正整数 $a$ 有 $f^{-1}(a)f^{-1}(1) = f^{-1}(a) = f^{-1}(a \cdot 1)$

    • proof