自动搬运

查看原文

来自洛谷，原作者为

	zhang_Jimmy Geography Monitor.

搬运于2025-08-24 22:51:01，当前版本为作者最后更新于2023-10-05 09:35:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到这题，我们想到的最直接的思路就是从 $l$ 遍历到 $r$，算出阶乘然后取最大值。但是这样显然会超时。

于是我们可以用一个辅助数组 $a$，用空间来换时间。

正确思路：

首先计算出 $l! \bmod k$ 的值，将其存在 $a_l$ 里。

接下来，我们按照这样的规律来计算：

为什么呢？

这样想一下：

我们已经计算出了 $3! = 6$，现在要计算 $4!$。

$3! = 1 \times 2 \times 3$，$4! = 1 \times 2 \times 3 \times 4$。

可以发现后者比前者刚好多乘了一个 $4$。

那么这个性质可以得到推广：

对于任意一个 $i!$，都有 $i! = (i - 1)! \times i$。

总结出来这个公式后，结合题目，就可以得到 $a_i = a_{i - 1} \times i \bmod k$ 这个公式了。

代码如下：

#include <bits/stdc++.h>
using namespace std;

long long l, r, k, ans = INT_MIN, a[2000010]; 

long long jc(long long n){
	long long sum = 1;
	for(int i = 1; i <= n; i ++){
		sum = sum * i % k;
	}
	return sum;
}

int main(){
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	cin >> l >> r >> k;
	ans = max(ans, jc(l));
	a[l] = jc(l);
	for(int i = l + 1; i <= r; i ++){
		a[i] = a[i - 1] * i % k;
		ans = max(ans, a[i]);
	}
	cout << ans;
	return 0;
}