P9707 [KMOI R1] 音波武器题解

szh_AK_all · 2023-10-05 08:01:31 · 题解

题意

给出 l 和 r，要我们求出从 l 的阶乘到 r 的阶乘中对 k 取模的最大值。

分析

不难发现，对于 l!,(l+1)!,(l+2)!...(r-1)!,r!，后一项都是前一项的倍数，所以，不难推出：(i+1)! \equiv i!\times(i+1) \pmod k，其中 i 为非负整数。

由此，我们就得到了一个递推式。由于 l,r,k 不可能为 0，所以，我们不妨设递推的第 0 项为 1，然后依次递推，记录其中大于等于 l 并且小于等于 r 的值的最大值即可。

Code

#include<bits/stdc++.h>
using namespace std;
long long a[2000005];
int main()
{
    int l,r;
    long long k;
    cin>>l>>r>>k;
    a[0]=1;
    long long ans=0;
    for(int i=1;i<=r;i++)
    {
        a[i]=a[i-1]*(i%k)%k;
        if(i>=l)
        ans=max(ans,a[i]);
    }
    cout<<ans;
}