C. [CSP-S-- 三十连测第二十七套]--T3--fac - S---【云智计划】---6月30日---模拟测#27 div2【补题】 - 比赛 - 梦熊联盟 (mna.wang)
题意
\(n\) 次询问，给定 \(a, k\)。
有一个可重集合，初始只有一个元素 \(a\)。每次操作将集合中所有元素替换为它的所有约数。求 \(k\) 次操作后集合内的元素和。
输出每次询问的答案的和。模 \(10^9 + 7\)，
\(n,a_i \le 10^6\)，\(k \le 10^{18}\)。
做法
问题可以转化成，每次可以将 \(a\) 替换为它的任意一个约数（可以是本身或 \(1\)）。求所有经过 \(k\) 次操作的方案最终的得到的数的和。
首先考虑如果 \(a\) 中本质不同的质因子个数不超过 \(1\) 的情况，即 \(a\) 可以表示成 \(p^x\) 其中 \(p\) 是质数的形式。
设 \(f(p, x)\)（其中 \(p\) 是质数）表示将 \(p^x\) 通过 \(k\) 次操作可以达到的数的和。
因为 \(p\) 是质数，所以 \(p^x\) 的约数一定可以表示成 \(p^y\) 的形式，其中 \(0 \le y \le x\)。我们分类讨论最终的得到的数 \(p_y\)：
-
\(y = 0\)：即从 \(p^x\) 变到了 \(p^0 = 1\)。由于其权值是 \(1\) 所以其贡献为其方案数。考虑计算其方案数。注意到每次操作相当于将指数 \(x\) 减去一个非负整数。所以我们要算有多少种从 \(x\) 变到 \(0\) 的 \(k\) 步操作，每步需要将 \(x\) 减去一个非负整数。插板法即可。答案为 \(\dbinom{x+k-1}{k-1}\)。
-
\(y \ge 1\)：注意到 \(p^x \rightsquigarrow p^y\) 的方案与 \(p^{x-1} \rightsquigarrow p^{y-1}\) 的方案一一对应，所以可以直接调用 \(f(p, x - 1)\)。但是这样最终得到的数是 \(p^{y-1}\) 而不是 \(p^y\)，所以要再乘上 \(p\)。答案为 \(f(p, x - 1) \times p\)。
所以：
\[f(p,x)=\begin{cases} 1&x=0\\ p\times f(p,x-1)+\dbinom{x+k-1}{k-1}& x \ge 1 \end{cases} \]打标发现若令 \(g(x)\) 表示 \(x\) 通过 \(k\) 次变化后得到的答案，那么 \(g\) 是积性函数。即可以将 \(x\) 分解质因数然后将每个质因数的答案相乘。
而每个质因数的答案我们已经做好了，是 \(f\)。所以一般的 \(x\) 的答案也可以计算了。
#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7, N = 1e6 + 10;
map<int, int> f[N];
long long k;
int fpm(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = 1ll * res * a % P;
b >>= 1, a = 1ll * a * a % P;
}
return res;
}
int C(long long n, int m) {
int res = 1;
for (long long i = n; i >= n - m + 1; -- i ) res = 1ll * i % P * res % P;
for (int i = 1; i <= m; ++ i ) res = 1ll * res * fpm(i, P - 2) % P;
return res;
}
int dp(int x, int y) {
if (!y) return 1;
if (f[x].count(y)) return f[x][y];
return f[x][y] = (1ll * dp(x, y - 1) * x % P + C(y + k - 1, y)) % P;
}
int p[N], cnt, mn[N];
signed main() {
freopen("fac.in", "r", stdin);
freopen("fac.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
mn[1] = 1;
for (int i = 2; i < N; ++ i ) {
if (!mn[i]) mn[i] = i, p[ ++ cnt] = i;
for (int j = 1; j <= cnt && p[j] <= (N - 1) / i; ++ j ) {
mn[p[j] * i] = p[j];
if (i % p[j] == 0) break;
}
}
int q, res = 0;
cin >> q >> k;
while (q -- ) {
int x;
cin >> x;
int ans = 1;
int lst = -1;
int cnt = 0;
while (x != 1) {
int p = mn[x];
if (lst != -1 && p != lst) {
ans = 1ll * ans * dp(lst, cnt) % P;
cnt = 0;
}
lst = p;
cnt ++ ;
x /= p;
}
ans = 1ll * ans * dp(lst, cnt) % P;
res = (res + ans) % P;
}
cout << res << '\n';
return 0;
}