P9707 [KMOI R1] 音波武器 题解

tder · 2023-10-05 10:16:15 · 题解

\Large\color{black}\textbf{P9707 [KMOI R1] 音波武器} \Large\textbf{题解}

\textbf{题目传送门}

\textbf{更好的阅读体验}

前缀积 + 枚举

求对于 i\in[l,r],\max(i!\bmod m)。

令 f_i 表示 i!，则可用递推预处理 f_0 至 f_r，即 f_i=\begin{cases}1&i=0.\\f_{i-1}\times i&\text{otherwise.}\end{cases}，再以此枚举 \forall i\in[l,r]，打擂台求出 f_i\bmod m 的最大值即可。

注意每次递推都要模 k。

注：(2\times10^6)!\approx10^{11733475}。所以说高精度也不是不行。

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int N = 2e6 + 5;
int l, r, k, f[N], ans;
signed main() {
    cin>>l>>r>>k;
    f[0] = 1; // 0! = 1
    for(int i = 1; i <= r; i++) {
        f[i] = f[i - 1] * i; // 递推求最大值
        f[i] %= k; // 注意每一步都要去模，防止炸裂
    }
    for(int i = l; i <= r; i++) 
        ans = max(f[i] % k, ans); // 打擂台取最大值
    cout<<ans;
    return 0;
}