题解 CF757E 【Bash Plays with Functions】

STDquantum · 2020-10-09 12:24:19 · 题解

虽然已经有题解了，我就讲得详细一点，做一下对上一篇的补充吧。

把题中 p,q 换成 a,b，因为 p 一般代表质数。

首先观察 f_0 的定义：满足 a\cdot b=n 且 \gcd(a,b)=1 的有序对 (a,b) 个数。

由于 \gcd 为 1，a 与 b 互质，则 a 和 b 没有公共的质因子。又因为 a\cdot b=n，所以 a 和 b 平分了 n 的所有质因子。

由算术基本定理，有 n=p_1^{k_1}p_2^{k_2}\cdots p_{\omega(n)}^{k_{\omega(n)}}，其中 p 是质数，\omega(n) 即 n 的不同质因子个数。

（\omega(n) 是加性函数，即对于 \gcd(i,j)=1，有 \omega(i\cdot j)=\omega(i)+\omega(j)）。

那么对于每个 p_i^{k_i}，必定为 a 或 b 的因子。所以把这些 p_i^{k_i} 分成两份（可为空），方案数即为 2^{\omega(n)}。

也就是说 f_0(n)=2^{\omega(n)}。

对于形如 C^{f} 的函数，C 为常数，f 为加性函数，则 C^f 为积性函数。因为乘法到了指数上就变成了加法。

由此可以得到 f_0 为积性函数。

其取值如下（其实前两个都可以通过第三个推导出来，但是由于后文要用到，所以单列出来）：

然后再来看 r\ge1 的情况：

乍一看无从下手，可以尝试将其展开。

由于 (u,v) 为有序数对并且不要求互质，可以令 \displaystyle u=d,v=\frac nd，其中 d\mid n。

又可以发现每个 d 与 \displaystyle \frac nd 是对称的，所以在枚举过程中被枚举了两次（对于 \displaystyle d=\frac nd 也是如此，只不过是枚举一次计算了两次），于是这个式子可以进一步简化为：

发现这是一个狄利克雷卷积的形式，若有 f_{r-1} 为积性函数，那么 f_r 就是积性函数。递归下去，f_0 是积性函数，所以 f_r 也为积性函数。

推出了 f_r 的积性，现在考虑如何计算答案 f_r(n)。

只有一个质因子的时候 f_0(p^k)=2，因此 f_r(p^k) 是和 p 无关的量，于是这启发我们可以把 r 与 k 单独拿出来考虑。

这样考虑计算答案也是没问题的，因为 f_r 是积性函数，即 \displaystyle f_r(n)=\prod_{k=1}^{\omega(n)}f_r(p^k)。

所以现在问题就变成了如何计算出 f_r(p^k)。

由定义可知 \displaystyle f_r(p^k)=\sum_{i=0}^kf_{r-1}(p^i)，所以我们考虑一个 DP。设 dp_{i,j} 表示 f_i(p^j)，那么初始化就是 dp_{i,0} = 1, dp_{0,j}=2(j\ge1)。转移时依照上式，\displaystyle dp_{i,j}=\sum_{x=0}^jdp_{i-1,x}。用前缀和优化一下。

第二维大小：20，因为 2^{19}\lt10^6\lt2^{20}。

#include <bits/stdc++.h>
using namespace std;

namespace STDquantum {

template <typename T> inline void read(T &x) {
    char ch;
    while (ch = getchar(), ch > '9' || ch < '0') {}
    x = (ch ^ 48);
    while (ch = getchar(), ch >= '0' && ch <= '9')
        x = x * 10 + (ch ^ 48);
}
template <typename T> inline void write(T x) {
    static int stk[100], top = 0;
    if (x == 0) return (void)putchar('0');
    if (x < 0) x = -x, putchar('-');
    while (x) stk[++top] = x % 10, x /= 10;
    while (top) putchar(stk[top--] + '0');
}

typedef long long ll;
const int N = 1e6 + 10, K = 20, mod = 1e9 + 7;

int low[N];
void getPrime() { // 直接筛质数分解n会T飞，所以记录n的最大质因子
    for (int i = 2; i < N; ++i) {
        if (!low[i]) {
            for (int j = i; j < N; j += i) { low[j] = i; }
        }
    }
}

int dp[N][K], sum[K] = {1}; // sum[0]是一
void init() {
    getPrime();
    for (int i = 0; i < N; ++i) { dp[i][0] = 1; }
    for (int i = 1; i < K; ++i)
        dp[0][i] = 2, sum[i] = sum[i - 1] + dp[0][i];
    for (int i = 1; i < N; ++i) {
        for (int j = 1; j < K; ++j) {
            dp[i][j] = sum[j];
            sum[j] = (sum[j - 1] + dp[i][j]) % mod; // 前缀和
        }
    }
}

int r, n, q;
ll ans = 1;
inline void main() {
    init();
    for (read(q); q--; ans = 1) {
        read(r), read(n);
        int cnt, p;
        while (n != 1) {
            cnt = 0, p = low[n];
            while (n % p == 0) ++cnt, n /= p;
            ans = ans * dp[r][cnt] % mod;
        }
        write(ans), putchar('\n');
    }
}

}    // namespace STDquantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
    freopen("D:\\OI\\STDquantum\\test.in", "r", stdin);
    freopen("D:\\OI\\STDquantum\\test.out", "w", stdout);
#endif
#ifndef LOCAL
    freopen("CF757E_Bash_Plays_with_Functions.in", "r", stdin);
    freopen("CF757E_Bash_Plays_with_Functions.out", "w", stdout);
#endif
#endif
    STDquantum::main();
    return 0;
}