前置技能

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

数论函数

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

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

积性函数

对于一个数论函数$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)}) \times 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$，不妨开个数组直接记忆化保存即可

代码

#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);
}