题解：P12470 [Math×Girl] 互质与整除

· · 题解

对于任意正整数 x，若其标准质因数分解为 x = \prod q_i^{\beta_i}，则有

\varphi(x) = \prod q_i^{\beta_i-1}(q_i-1)

这时候看看题目，由于 n 的质因子只有 p_1, p_2, \dots, p_s，我们可以得出以下两个必要条件：

  1. 对于 x 的任意质因子 q_i，必定满足 q_i-1 \mid n，即 q_i-1 必是 n 的约数。

  2. 如果某个质因子在 x 中的指数 \beta_i > 1，则 \varphi(x) 中就会产生 q_i 这个因子。所以若 \varphi(x) \mid n，那 q_i 必须是 n 的质因子之一，即 q_i \in \{p_1, \dots, p_s\}。

做质数筛时可以用 米勒-拉宾素性检验，将每一个约数加 1 判断是否为质数。

将 n 的质因数分解形式看作一个多维背包的容量：背包有 s 个维度，第 i 维的容量上限是 \alpha_i。挑选合适的质数 q 来构成 x。

我们定义背包里的“物品”合法的条件为，遍历 n 的所有约数 d，若 q = d + 1 是质数，则 q 就是一个合法的“物品”。它消耗的背包体积，必是 d 的质因数分解结果。

则如果我们要将物品分类，就可以分为以下两种。

  1. 如果 q 不在 \{p_1, \dots, p_s\} 中，根据条件 2，它的指数 \beta 只能为 1，则这种物品最多只能被选一次，即为 0/1 背包。

  2. 如果 q = p_k，它的指数 \beta 可以大于 1。选第 1 次时，消耗的体积是 p_k-1 的质因数分解；从选第 2 次开始，每次只需消耗 1 个 p_k，即为完全背包。

到这里基本就结束了。接下来就是递归遍历所有合法的多维体积，然后滚动数组状态转移即可。完全背包也可以用前缀和优化同维转移。

质数筛最劣复杂度是 O(D \cdot k \log n)，其中 k 是选取的底数个数。而背包 dp 的时间复杂度理论上限是 O(V \times D)，所以总时间复杂度是 O(D \log n + V \times D)。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int qcnt, ctmp[16], palp[16], pc[16], pstr[16];
template<typename T>
inline void read(T &x) {
    x = 0;
    T f = 1;
    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(); }
    x *= f;
}

template<typename T>
inline void write(T x, char ec = '\n') {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10, 0);
    putchar(x % 10 + '0');
    if (ec) putchar(ec);
}

template<typename T>
inline T qpow(T a, T b, T m) {
    T ans = 1;
    a %= m;
    while (b) {
        if (b & 1) ans = (ans * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return ans;
}

template<typename T>
inline T gcd(T a, T b) {
    return b ? gcd(b, a % b) : a;
}

using u64 = unsigned long long;
using u128 = __uint128_t;

inline u64 qp_mr(u64 a, u64 b, u64 m) {
    u64 rs = 1;
    a %= m;
    while (b) {
        if (b & 1) rs = (u128)rs * a % m;
        a = (u128)a * a % m;
        b >>= 1;
    }
    return rs;
}

bool is_prm(u64 n) {
    if (n < 2) return false;
    if (n == 2 || n == 3 || n == 5 || n == 7 || n == 11) return true;
    if (n == 13 || n == 17 || n == 19 || n == 23 || n == 29) return true;
    if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0 || n % 11 == 0) return false;
    if (n % 13 == 0 || n % 17 == 0 || n % 19 == 0 || n % 23 == 0 || n % 29 == 0) return false;
    u64 d = n - 1;
    int s = 0;
    while ((d & 1) == 0) { d >>= 1; ++s; }
    static const u64 base[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    for (u64 a : base) {
        u64 p = a % n;
        if (p == 0) continue;
        u64 x = qp_mr(p, d, n);
        if (x == 1 || x == n - 1) continue;
        bool ok = false;
        for (int i = 1; i < s; ++i) {
            x = (u128)x * x % n;
            if (x == n - 1) { ok = true; break; }
        }
        if (!ok) return false;
    }
    return true;
}

struct Prm {
    u64 q;
    int c[16];
    int pk;
};

Prm Q[105000];
int poff, ppk, ps, dp[105000];
u64 p[16];

void getQ(int d, u64 cur) {
    if (d == ps) {
        u64 q = cur + 1;
        if (is_prm(q)) {
            int pk = -1;
            for (int i = 0; i < ps; ++i) {
                if (q == p[i]) { pk = i; break; }
            }
            Q[qcnt].q = q;
            for (int i = 0; i < ps; ++i) Q[qcnt].c[i] = ctmp[i];
            Q[qcnt].pk = pk;
            qcnt++;
        }
        return;
    }
    u64 ppow = 1;
    for (int i = 0; i <= palp[d]; ++i) {
        ctmp[d] = i;
        getQ(d + 1, cur * ppow);
        if (i < palp[d]) ppow *= p[d];
    }
}

void upd(int d, int id, int ek) {
    if (d == ps) {
        if (ppk == -1) {
            int prv = id - poff;
            dp[id] += dp[prv];
            if (dp[id] >= MOD) dp[id] -= MOD;
        } else {
            unsigned long long sm = 0;
            int mxb = ek - pc[ppk] + 1;
            int cid = id - poff;
            for (int b = 1; b <= mxb; ++b) {
                sm += dp[cid];
                cid -= pstr[ppk];
            }
            dp[id] = (dp[id] + sm) % MOD;
        }
        return;
    }
    for (int e = palp[d]; e >= pc[d]; --e) {
        upd(d + 1, id + e * pstr[d], d == ppk ? e : ek);
    }
}

void solve() {
    read(ps);
    for (int i = 0; i < ps; ++i) {
        read(p[i]);
        read(palp[i]);
    }
    pstr[0] = 1;
    for (int i = 0; i < ps; ++i) {
        pstr[i + 1] = pstr[i] * (palp[i] + 1);
    }
    int dpsz = pstr[ps];
    for (int i = 0; i < dpsz; ++i) dp[i] = 0;
    dp[0] = 1;
    qcnt = 0;
    getQ(0, 1);
    for (int i = 0; i < qcnt; ++i) {
        ppk = Q[i].pk;
        poff = 0;
        for (int j = 0; j < ps; ++j) {
            pc[j] = Q[i].c[j];
            poff += pc[j] * pstr[j];
        }
        upd(0, 0, 0);
    }
    unsigned long long ans = 0;
    for (int i = 0; i < dpsz; ++i) {
        ans += dp[i];
    }
    ans %= MOD;
    write(ans);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; read(t);
    while (t--) solve();
    return 0;
}