题目出自東京工業大学プログラミングコンテスト2019（TTPC2019）

题目链接 https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_i

题意

对于正整数 \(x\) 定义函数 \[ f(x) := \begin{cases} f(\frac{x}{P}) \quad & \text{if $x \equiv 0 \pmod{P}$} \\ x & \text{otherwise} \end{cases} \]

给你整数 \(P, Q, L, R\)，输出下列式子的值 \[ \left(\prod_{i=L}^{R} f(i) \right) \bmod Q \]

限制

• \(2 \le P, Q \le 10^7\)
• \(1 \le L \le R \le 10^{18}\)

解法

思路：把 \(L\) 到 \(R\) 的整数分成两类

• 能被 \(P\) 整除的
• 不能被 \(P\) 整除的

前者对答案的贡献归结为 \(\left(\prod_{i = \ceil{L/P}}^{\floor{R/P}} f(i)\right) \bmod Q\)，可以递归处理。

后者对答案的贡献就是它们的乘积除以 \(Q\) 的余数。自然地，我们考虑以 \(Q\) 为周期来处理 \(L, \dots, R\) 中不能被 \(P\) 整除的那些整数。问题在于，一般来说，每个周期内能被 \(P\) 整除的那些数并不都是同一批。

实际上，我们需要把周期扩大到 \(\lcm(P, Q)\)。

解决这个困难需要一个关键的观察：

当 \(\lcm(P, Q)\) 大于 \(Q\) 时，也就是 \(P\) 不能整除 \(Q\) 时，如果 \(L, \dots, R\) 中有两个相邻的 \(Q\) 的倍数，\(nQ\) 和 \((n+1)Q\)，那么这两个数不都能被 \(P\) 整除。

若不然就有二者的差，也就是 \(Q\)，能被 \(P\) 整除。矛盾。

这时，乘积 \(\prod_{i=L}^{R} f(i)\) 是 \(P\) 的倍数。

注意到：

连续 \(2Q\) 个整数中至少有两个是 \(Q\) 的倍数。

因此当 \(P\) 不能整除 \(Q\) 且 \(R - L + 1 \ge 2Q\) 时，答案是 \(0\)。

当 \(P\) 整除 \(Q\) 时，我们就能以 \(Q\) 为周期来处理 \(L, \dots, R\) 中不能被 \(P\) 整除的数。

代码

int P, Q;

long long f(long long x) {
    while (x % P == 0)
        x /= P;
    return x;
}

long long power(long long x, long long n) { // 快速幂
    long long ans = 1;
    while (n > 0) {
        if (n & 1)
            ans = ans * x % Q;
        x = x * x % Q;
        n >>= 1;
    }
    return ans;
}

vector<long long> suff, pref;

long long solve(long long l, long long r) { // [l, r)
    if (r - l < Q) {
        long long ans = 1;
        for (long long i = l; i < r; i++) {
            ans = ans * (f(i) % Q) % Q;
        }
        return ans;
    }
    long long lp = (l - 1) / Q + 1, rp = r / Q;
    return solve((l + P - 1) / P, (r + P - 1) / P) * power(pref[Q], rp - lp) % Q * suff[l % Q] % Q * pref[r % Q] % Q;
}

int main() {
    long long L, R;
    cin >> P >> Q >> L >> R;
    R++; // 采用左闭右开的方式表示区间
    
    if (Q % P) {
        long long ans = 0;
        if (R - L < 2 * Q) { // 暴力计算
            ans = 1;
            for (long long x = L; x < R; x++) {
                ans = ans * (f(x) % Q) % Q; // ans * f(x) 可能爆 long long
            }
        }
        cout << ans << '\n';
        return 0;
    }

    pref.assign(Q + 1, 1); // pref[i]: 0,...,i-1 中不能被 P 整除的数的乘积，模 Q
    for (int i = 0; i < Q; i++) {
        if (i % P) {
            pref[i + 1] = pref[i] * i % Q;
        } else {
            pref[i + 1] = pref[i];
        }
    }

    suff.assign(Q, 1);
    long long t = 1;
    for (int i = Q - 1; i >= 1; i--) {
        if (i % P) {
            t = t * i % Q;
        }
        suff[i] = t;
    }
    cout << solve(L, R) << '\n';
}