数论数论函数基础知识

基本符号

\((a,b)=\gcd(a,b)\)
\(a \bot b \Leftrightarrow (a,b)=1\)
\([\mathrm{expr}]=0/1\)如果表达式为真，那么值为\(1\)，否则为\(0\).

积性函数

基本概念：对于一个数论函数\(f(n)\)，当\(n \bot m\)时，满足\(f(nm)=f(n)f(m)\)，那么就称\(f(n)\)是一个积性函数。

完全积性函数：如果\(n,m\)不互质的时候仍然满足\(f(nm)=f(n)f(m)\)，那么就称\(f(n)\)是一个完全积性函数。

完全积性函数是积性函数的一个子集

一些基本的积性函数

元函数(或称为单位元):\(\epsilon(n)=[n=1]\),判断\(n\)是否为\(1\)。

恒等函数:\(I(n)=1\),无论\(n\)取何值，函数值都为\(1\)。

单位函数:\(\mathrm{id}(n)=n\),等于\(n\)自身。

欧拉函数:\(\varphi(n)=\sum\limits_{i=1}^n [i \bot n]\),\(n\)以内和\(n\)互质的数的个数。

约数函数:\(d(n)=\sum\limits_{i=1}^n [i|n]=\sum\limits_{d|n} 1\)，其前缀和有一个\(O(\sqrt{n})\)方法求解：

\[\sum\limits_{i=1}^n d(i)=\sum\limits_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor \]

欧拉函数存在一些简单有用的性质：

\[\sum\limits_{d|n}\varphi(d)=n\\ \sum\limits_{i=1}^n [i \bot n]\times i=\frac{n\times\varphi(n)}{2}\\ \varphi(nm)=\frac{\varphi(n)\varphi(m)(n,m)}{\varphi((n,m))} \]

对于第二个性质，稍微给一个小证明：

因为\(\gcd(x,n)=\gcd(n-x,n)\)所以\(n\)以内和\(n\)互质的数一定成对出现，并且他们的和一定为\(n\)，这样的数对一定有\(\cfrac{\varphi(n)}{2}\)个，所以这些数的总和为\(\cfrac{n\times\varphi(n)}{2}\)。

莫比乌斯函数:\(\mu(i)\)，它的定义和求值方式之后再说。

狄利克雷卷积

现在有两个数论函数\(f(n),g(n)\),他们的狄利克雷卷积表示为\((f*g)(n)\)，两个积性函数的卷积一定是一个积性函数。

\[(f*g)(n)=\sum\limits_{d|n}f(d)g\left(\frac{n}{d}\right) \]

上面欧拉函数的其中一条性质用狄利克雷卷积表示就是\((\varphi*I)(n)=\mathrm{id}(n)\)

逆元:如果说\((f*g)(n)=\epsilon(n)\)，那么就称\(f\),\(g\)互为逆元，\(g\)可以写为\(f^{-1}\)。一个积性函数的逆元一定是一个积性函数

单位元:\((f*\epsilon)=f\)

结合律:\((f*g)*k=f*(g*k)\)

莫比乌斯反演

首先解释一下,之前说的\(\mu(n)\),其实就是\(I(n)\)的逆元。接下来我们推一下这个函数的求值方式。

因为\(\mu(n)\)是一个积性函数，所以可以分开每个质因子进行考虑。

对于\(\mu(p^k)\)

若\(k=0\)，易得\(\mu(1)=1\),

若\(k=1\)，因为\((I*\mu)(p)=0\Rightarrow I(1)\mu(p)+I(p)\mu(1)=0\Rightarrow \mu(p)=-1\)

若\(k>2\)，可以得到

\[(I*\mu)\left(p^k\right) =\sum_{d=0}^k \mu\left(p^d\right)I\left(p^{k-d}\right) =\sum_{d=0}^k \mu\left(p^d\right) \]

可以发现，如果\(k=2\),因为\(\mu(1)=1,\mu(p)=-1\)，那么\(\mu(p^2)=0\),以此类推，可以得到：

\[\forall~~k>1, \mu(p^k)=0 \]

接着考虑所有正整数的情况：

\[对n进行质因数分解，得到n=\prod\limits_{i=1}^n c_i^{k_i}\\ \mu(n)=\begin{cases} 0 &存在k_i>1\\ (-1)^n &otherwise \end{cases} \]

莫比乌斯反演，实际上是对于两个函数进行的变换：

\[F(n)=\sum\limits_{d|n}f(d)\Leftrightarrow f(n) =\sum\limits_{d|n}\mu\left(\frac{n}{d}\right)F(d) \]

这个实际上证明非常简单，将其转化为狄利克雷卷积的形式：

\[\begin{aligned} &F(n)=(f*I)(n)\\ \Rightarrow& (F*\mu)(n)=(f*I*\mu)(n)\\ \Rightarrow& (F*\mu)(n)=f(n) \end{aligned} \]

小例题(有点难度)

解法可能和莫比乌斯没有任何关系。

给定一个正整数\(n(n\leq 10^{14})\)，计算

\[\left(\sum\limits_{i=1}^n\sum\limits_{d|i} \gcd\left(d,\frac{i}{d}\right)\right)\mod (10^9+7) \]

直接画柿子即可：

\[\begin{aligned} &\sum\limits_{i=1}^n \sum\limits_{d|i} (\varphi*I)\left(\gcd\left(d,\frac{i}{d}\right)\right)\\ =&\sum\limits_{i=1}^n \sum\limits_{d|i} \sum\limits_{k|d,k|\frac{i}{d}} \varphi(k)\\ =&\sum\limits_{i=1}^n \sum\limits_{k^2|i} \varphi(k) \sum\limits_{d=1}^{\lfloor\frac{n}{i}\rfloor} 1\\ =&\sum\limits_{i=1}^n \sum\limits_{k^2|i} \varphi(k)\times \left\lfloor\frac{n}{i}\right\rfloor\\ =&\sum\limits_{k=1}^{\lfloor{\sqrt{n}}\rfloor} \varphi(k) \sum\limits_{i=1}^{\left\lfloor{\frac{n}{k^2}}\right\rfloor} \left\lfloor{\frac{n}{ik^2}}\right\rfloor \end{aligned} \]

可以发现，前半部分可以使用前缀和进行计算，而后半部分可以使用整除分块。

杜教筛

现在我们需要求出一个积性函数的前缀和，
假设为\(f(n)\)。
而\(S_f(n)=\sum\limits_{i=1}^n f(i)\)。如果n较小，可以使用线性筛求出。

但是\(n>10^7\)，现在需要一种较为快速的计算方法。

由于\(f\)是一个积性函数，可以构造两个积性函数\(g,h\)，满足\((g*f)(n)=h(n)\)。而\(g,h\)都很容易求出。而\(h\)的前缀非常容易求出，而\(g(1)\)的逆元很容易求。

\[\begin{aligned} \sum\limits_{i=1}^n h(i) &=\sum\limits_{i=1}^n \sum\limits_{d|i} f(i)\left(\frac{d}{i}\right)\\ &=\sum\limits_{d=1}^n g(d) \sum\limits_{i=1}^{\left\lfloor\frac{i}{d}\right\rfloor} f(i)\\ &=\sum\limits_{d=1}^n g(d) S_f\left(\left\lfloor{\frac{n}{d}}\right\rfloor\right)\\ &= g(1)S(n) + \sum\limits_{d=2}^n g(d) S_f\left(\left\lfloor{\frac{n}{d}}\right\rfloor\right)\\ g(1)S(n) &= \sum\limits_{i=1}^n h(i) - \sum\limits_{d=2}^n g(d) S_f\left(\left\lfloor{\frac{n}{d}}\right\rfloor\right) \end{aligned} \]

在实际实现的时候，在复杂度允许的情况下，用线性筛先将\(n\)较小的前缀和求出，在调用函数的时候，用一个unordered_map保存前缀和，就能加快运算。

构造例子

Example 1:\(f\rightarrow \mu\), 可以考虑构造\(g\rightarrow I, h\rightarrow \epsilon\)

Example 2:\(f\rightarrow \varphi\), 考虑式子\((\varphi*I)=\mathrm{id}\)，构造\(g\rightarrow I,h\rightarrow \mathrm{id}\)

Example 3:\(f\rightarrow \mathrm{id}\times\mu\), 可以考虑构造\(g\rightarrow \mathrm{id}\)，那么

\[\begin{aligned} (g*f)(n) &=\sum\limits_{d|n} g\left(\frac{n}{d}\right)f(d)\\ &=\sum\limits_{d|n} \frac{n}{d} \times \mu(d) \times d\\ &= n\sum\limits_{d|n} \mu(d)\\ &= n[n=1]\\ &= \epsilon(n) \end{aligned} \]

所以\(h\)函数就是\(\epsilon\)。

Example 4:\(f\rightarrow \mathrm{id}^2 \times \varphi\)。
构造\(g(n)=\mathrm{id}(n)^2\), 那么可以得到：

\[\begin{aligned} (f*g)(n) &=\sum\limits_{d|n} g\left(\frac{n}{d}\right)f(d)\\ &=\sum\limits_{d|n} \left(\frac{n}{d}\right)^2 \times d^2 \times \varphi(d)\\ &=n^2 \sum\limits_{d|n}\varphi(d)\\ &=n^3 \end{aligned} \]

所以\(h\)函数就是\(\mathrm{id}^3\)。

附录：积性函数的线性筛法

以\(\varphi\)为例：

void init() {
  phi[1] = 1;
  for (int i = 2; i < MAXN; ++i) {
    if (!vis[i]) {
    	//i是一个质数
      phi[i] = i - 1;
      pri[cnt++] = i;
    }
    for (int j = 0; j < cnt; ++j) {
      if (1ll * i * pri[j] >= MAXN) break;
      vis[i * pri[j]] = 1;
      if (i % pri[j]) {
        phi[i * pri[j]] = phi[i] * (pri[j] - 1);
      } else {
        phi[i * pri[j]] = phi[i] * pri[j];
        break;
      }
    }
  }
}