Link。
朴素 dp 应该不用说了。放个用 map 的代码。
int dfs(int n, int k) {
if (!k) return n;
if (f[make_pair(n, k)]) return f[make_pair(n, k)];
int tot = 0, ans = 0;
for (int i = 1; i * i <= n; i++) {
if (n % i) continue;
ans = (ans + dfs(i, k - 1)) % MOD;
tot++;
if (i != n / i) {
ans = (ans + dfs(n / i, k - 1)) % MOD;
tot++;
}
}
return f[make_pair(n, k)] = ans * qkpow(tot, MOD - 2) % MOD;
}
然后我期待有什么神秘转化，妙妙思路，结果，，，你告诉我这是个积性函数？？？
Definition.
若函数 \(f(n)\) 满足 \(f(1) = 1\) 且 \(\forall x, y \in \mathbb{N_+}, \gcd(x, y) = 1\) 都有 \(f(xy) = f(x)f(y)\)，则 \(f(n)\) 为积性函数。
以前完全不知道的一个性质。哦好像讲欧拉函数的时候有提过。
证明这个玩意可以感性理解，\(f(x) = \dfrac{a_1 + a_2 + \dots + a_n}{n}, f(y) = \dfrac{b_1 + b_2 + \dots + b_m}{m}\)，然后因为 \(\gcd(x,y) = 1\)，\(a\) 和 \(b\) 除了 \(1\) 应该是没有重复的，\(xy\) 的因数也就是 \(a, b\) 中选出两个的乘积，跟定义是一样的。
然后就分解一下，\(n = p_1 ^ {\alpha_1}p_2 ^ {\alpha_2}\dots p_n ^ {\alpha_n}, p_1 < p_2 < \dots < p_n\)，相当于只需要算质数的次幂结果了。然后因为是质数的次幂，因数也只能是这个质数的次幂，上面的 dp 就是 \(O(\alpha k)\) 的了，最后乘起来即可。
namespace liuzimingc {
const int N = 65, K = 1e4 + 5, MOD = 1e9 + 7;
#define endl '\n'
#define int long long
int n, k, f[N][K], ans = 1, p;
int qkpow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = ans * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return ans;
}
int dfs(int n, int k) { // p ^ n, k
if (!n) return 1;
if (!k) return qkpow(p, n);
if (f[n][k]) return f[n][k];
int ans = 0;
for (int i = 0; i <= n; i++)
ans = (ans + dfs(n - i, k - 1)) % MOD;
return f[n][k] = ans * qkpow(n + 1, MOD - 2) % MOD;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> k;
for (p = 2; p * p <= n; p++) {
if (n % p) continue;
int tot = 0;
while (n % p == 0) n /= p, tot++;
// cout << tot << endl;
ans = ans * dfs(tot, k) % MOD;
for (int i = 1; i <= tot; i++)
for (int j = 1; j <= k; j++)
f[i][j] = 0;
}
if (n > 1) {
p = n;
ans = ans * dfs(1, k) % MOD;
}
cout << ans << endl;
return 0;
}
#undef int
} // namespace liuzimingc