[TTPC2019 Task I] I Hate P
题目出自東京工業大学プログラミングコンテスト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';
}