前置技能

  • 数论函数
  • 积性函数
  • 完全积性函数
  • 整除
  • 素数

数论函数

定义在正整数集上的实值或复值函数

一般可视作定义域为正整数,值域为整数的函数

积性函数

对于一个数论函数$f$,若当$(a,b)=1$时,$f(ab)=f(a)f(b)$,则称其为积性函数

完全积性函数

对于一个数论函数$f$,若$f(ab)=f(a)f(b)$,则称其为完全积性函数

线性筛

前提

  • 积性函数$f$
  • 对于素数$p$,可以快速求出$f(p^k)$的值

步骤

线性筛一共会处理如下的数

  • 素数$p$
  • $i \times p$,其中$i$是任意正整数,且$p \nmid i$,且$p$是素数,且$p$是$i \times p$的最小素因子
  • $i \times p$,其中$i$是任意正整数, 且$p \mid i$,且$p$是素数,且$p$是$i$的最小素因子,且$p$是$i \times p$的最小素因子

处理

素数$p$

由于已经可以快速求出$f(p^k)$了,所以可以快速求出$f(p)$

$p \nmid i$

由于是积性函数,且$(p,i)=1$,因此$f(i \times p)=f(i) \times f(p)$

由于$i \le i \times p \wedge p \le i \times p$,所以可以计算出$f(i \times p)$

$p \mid i$

同时需要计算出来$g(n)$,表示$n$的最小素因数的乘积,即将$n$分解为$p_{min}^{k_{min}} \times t$的形式,其中$(p_{min}^{k_{min}},t)=1$

先假设会计算$g$了

那么$i \times p=\frac{i}{g(i)} \times g(i) \times p$,其中$(\frac{i}{g(i)} , g(i) \times p)=1$

因此$f(i \times p)=f(\frac{i}{g(i)},f(g(i) \times p))$

$g(i) \times p$可以分解为$p^k$的形式,如果需要用到$k$的话,可以在求$g$的时候顺便求一下$k$

由于$f(p^k)$可以快速求,所以就可以计算出$f(i \times p)$

计算$g,k$

依然是分成三类

素数$p$

$g(p)=p$

$k(p)=1$

$p \nmid i$

$g(i \times p)=p$

$k(i \times p)=1$

$p \mid i$

$g(i \times p)=g(i) \times p$

$k(i \times p)=k(i)+1$

应用

计算$\phi$

定义$\phi(n)=\sum_{i=1}^{n}\epsilon((i,n))$

同时有计算公式$\phi(n)=n\Pi \frac{p_i-1}{p_i}$

依旧是分类讨论

素数$p$

$\phi(p)=p-1$

因为$[1,p-1]$中所有的整数都和$p$互素

$p \nmid i$

$\phi(i \times p)=\phi(i) \times \phi(p)=\phi(i) \times (p-1)$

$\phi$是积性函数

$p \mid i$

设$\phi(i)=n \Pi \frac{p_i-1}{p_i}$

因为$i$中已经有素因子$p$

则$\phi(i \times p)=np \Pi \frac{p_i-1}{p_i}=p \times (n\Pi \frac{p_i-1}{p_i})$

也就是说$\phi(i \times p)=p \times \phi(i)$

计算$\mu$

定义

$$
\mu(n)=
\begin{cases}
1 \qquad & n=1 \\
(-1)^k \qquad & n=\Pi_{i=1}^{k} p_i \\
0 \qquad & \text{otherwise}
\end{cases}
$$

依旧是分类讨论

素数$p$

$\mu(p)=-1$

根据$\mu$的定义

$p \nmid i$

$\mu(i \times p)=\mu(i) \times \mu(p)=-\mu(i)$

$\mu$是积性函数

$p \mid i$

$\mu(i \times p)=\mu(\frac{i}{p^t} \times p^t)=\mu(\frac{i}{p^t}) \times \mu(p^t)=0 \wedge (\frac{i}{p^t},p^t)=1 \wedge t \ge 2$

根据$\mu$的定义,如果$n$包含非$1$的完全平方因子,那么$\mu(n)=0$

计算$\tau$

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

定义$\tau(n)=\sigma_0(n)$,叫做约数个数函数

则$\tau(n)=\Pi (a_i+1)$,其中$n=\Pi p_i^{a_i}$

素数$p$

$\tau(p)=2$

即$1$和$p$

$p \nmid i$

$\tau(i \times p)=\tau(i) \times \tau(p)$

$\sigma_k$是积性函数

$p \nmid i$

$\tau(i \times p)=\tau(\frac{i}{p^t}) \times \tau(p^t)=\tau(\frac{i}{p^t}) \times (t+1)$

计算$\sigma$

定义$\sigma(n)=\sigma_1(n)​$,叫做约数和函数

则$\sigma(n)=\Pi_i \sum_{j=0}^{a_i} p_i^j$

素数$p$

$\sigma(p)=1+p$

即$1$和$p$

$p \nmid i$

$\sigma(i \times p)=\sigma(i) \times \sigma(p)$

$\sigma_k$是积性函数

$p \mid i$

$\sigma(i \times p)=\sigma(\frac{i}{p^t}) \times \sigma(p^t)=\sigma(\frac{i}{p^t}) \times \sum_{j=0}^{t}p^j=\sigma(\frac{i}{p^t}) \times h(i)$

其中$h(i)$表示$i$的最小素因数的幂次和,这个可以在线性筛的同时处理

计算$\sigma_k$

base

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

$p \in P$

$\sigma_k(p)=\sum_{d \mid p}d^k=1+p^k$

$p \nmid i$

$\sigma_k(i \times p)=\sigma_k(i) \times \sigma_k(p)$

$p \mid i$

$i \times p=t \times p^r \wedge (t,p^r)=1$

$\sigma_k(i \times p)=\sigma_k(t) \times \sigma_k(p^r)$

$\sigma_k(p^r)=\sum_{j=0}^{r}(p^j)^k=\sum_{j=0}^{r}p^{jk}$

优化

当然这还是不够的,每次大力计算$\sigma_k(p^r)$是会超时的

不妨测一下$n=k=10^7$的时候,$p,r$的最大值吧

可以得到$p \le 4000, r \le 25$,不妨开个数组直接记忆化保存即可

代码

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
39
40
41
42
43
44
45
46
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N = 1e7 + 10, p = 1000000007;

int n, k, pri[N], tot, c[N], mn[N], g[N];

bool vis[N];

ll f[N], ans;

int pw(int a, ll b) {
int r = 1;
for( ; b ; b >>= 1, a = (ll) a * a % p) if(b & 1) r = (ll) r * a % p;
return r;
}

int val[4000][25];
inline int F(int mn, int c) {
if(val[mn][c] != -1) return val[mn][c];
int r = 0;
for(int j = 0 ; j <= c ; ++ j) r = ((ll) r + pw(mn, (ll) j * k)) % p;
return val[mn][c] = r;
}

int main() {
memset(val, -1, sizeof val);
scanf("%d%d", &n, &k);
ans = f[1] = 1;
for(int i = 2 ; i <= n ; ++ i) {
if(!vis[i]) pri[++ tot] = i, f[i] = 1 + pw(i, k), g[i] = i, c[i] = 1, mn[i] = i;
for(int j = 1 ; j <= tot && (ll) i * pri[j] <= n ; ++ j) {
int x = i * pri[j];
vis[x] = 1;
if(i % pri[j] == 0) {
f[x] = f[i / g[i]] * F(mn[i], c[i] + 1) % p;
g[x] = g[i] * pri[j];
c[x] = c[i] + 1;
mn[x] = pri[j];
break;
} else f[x] = f[i] * f[pri[j]] % p, g[x] = pri[j], c[x] = 1, mn[x] = pri[j];
}
ans = (ans + f[i]) % p;
}
printf("%lld\n", ans);
}