题解 CF1097D 【Makoto and a Blackboard】

我们考虑对于一个$N$，他如果变成了他的约数$x$，那又会变成一个子问题 我们定义$F(n, k)$为n操作k次的期望个数 那么我们有$F(n, k) =\sum_{x|n} F(x, k - 1) * \frac{1}{d}$（其中d为n的约数个数） 因为$N$的约数个数肯定在$\sqrt N$以内现在我们就有了一个$O(\sqrt N K)$的暴力了 前面的$\sqrt N$肯定是不能省略了，我们可不可以对$K$下手呢？ 我们考虑$N$是质数，那么答案为$\frac{N + 2^k - 1}{2^k}$ 再考虑一波$N = p^x$其中p是质数，那么我们考虑用上述$DP求解$ 设$dp[i][j] $为第i此操作后，为$p^j$的概率 $dp[i][j] = \sum_{l = j}^x dp[i - 1][l] * \frac{1}{j}$ 最后的答案为$\sum_{j = 1}^{x} dp[k][j] * p^j$ 我们发现每一个$p_i^{j}$互不影响，这又是一个积性函数 $sum[i][j] * sum[i][k] = sum[i][j * k](gcd(j, k) == 1)$ 证明的话我们一样回归定义，假设变成$p_1^j * p_2^0$的概率为x，$p_1^0 *p_2^k$的概率为y，那么$p_1^j*p_2^k$的概率一定为$x*y$ 于是我们只需要对$N$分解质因数后再套一个$\prod$即可 这样的复杂度是$\sqrt N + K * log^3N=10^9$ 但是由于$log$不一定为2，所以这个复杂度是可以过这道题的 # $Code:$ ``` #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cstdlib> using namespace std; #define il inline #define re register #define int long long #define mod 1000000007 il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define rep(i, s, t) for(re int i = s; i <= t; ++ i) #define mem(k, p) memset(k, p, sizeof(k)) #define maxn 1000005 int n, m, prim[maxn], tot, dis[maxn], dp[10005][50], ans, inv[100], Ans = 1; il void get(int x) { for(re int i = 2; i * i <= x; ++ i) { if(x % i == 0) prim[++ tot] = i; while(x % i == 0) x /= i, ++ dis[tot]; } if(x != 1) prim[++ tot] = x, ++ dis[tot]; } il int qpow(int a, int b) { int r = 1; while(b) { if(b & 1) r = r * a % mod; b >>= 1, a = a * a % mod; } return r; } signed main() { n = read(), m = read(); get(n); rep(i, 1, 60) inv[i] = qpow(i, mod - 2); rep(T, 1, tot) { mem(dp, 0), dp[0][dis[T]] = 1, ans = 0; rep(i, 1, m) { rep(j, 0, dis[T]) { rep(k, j, dis[T]) dp[i][j] = (dp[i - 1][k] * inv[k + 1] % mod + dp[i][j]) % mod; } } rep(i, 0, dis[T]) ans = (ans + dp[m][i] * qpow(prim[T] % mod, i) % mod) % mod; Ans = ans * Ans % mod; } printf("%lld", Ans); return 0; } ```