P9707 [KMOI R1] 音波武器 题解

· · 题解

思路：

由于数据中说：k \le {10^{12}}，很明显，假如结果刚好在 10^{12} - 1 的话，就会爆掉，因此需要用 long\ long。

假如我们每次都计算的话，就会超时，因此我们可以用一个数据，预处理 1 到 ~l-1 的数的阶乘，在挨个遍历 l 到 r 的数据就行了。

AC CODE:

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
long long a[N];
int main() {
    long long l, r, k;
    cin >> l >> r >> k;
    long long s = 0;
    a[0] = 1;
    for (int i = 1; i < l; i++)
        a[i] = a[i - 1] * i % k;
    for (int i = l; i <= r; i++) {
        a[i] = a[i - 1] * i % k;
        s = (a[i] > s ? a[i] : s);
    }
    cout << s;
    return 0;
}