题解：P8249 模法问题

Lfz312g · 2025-01-13 21:13:27 · 题解

Solition

思路分析

查询区间最值，自然想到使用 ST 表，但是值域过大，需要优化。
对于 i \bmod a + i \bmod b 其循环节长度 len = \operatorname{lcm}(a,b)。
查询时需要分类讨论。
如果 r-l +1 \ge n，这时此区间覆盖整个循环节，输出 [1,len] 的最大值。
如果 l \bmod len + 1 > r \bmod len +1 ，把区间拆分成 [1,l] 和 [r,len]，取最大值即可。
如果都不是，将 [l,r] 映射到 [l \bmod len +1,r \bmod len+1]，然后查询。

#include <bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
typedef long long ll;
int st[21][2000027],s[2000027],log_2[2000027],a,b,n;
void start() {
    ffor(i,1,n) st[0][i]=s[i];
    ffor(i,2,n) log_2[i]=log_2[i>>1]+1;
    for (int j=1;(1<<j)<=n;j++) for (int i=1;i<=n-(1<<j)+1;i++) st[j][i]=max(st[j-1][i],st[j-1][i+(1<<j-1)]);
}
int ask(int l,int r) {
    int k=log_2[r-l+1];
    return max(st[k][l],st[k][r-(1<<k)+1]);
}
int main()
{
    cin>>a>>b;
    n=a*b/__gcd(a,b);
    ffor(i,0,n-1) s[i+1]=(i%a+i%b); 
    start();
    int q;
    cin>>q;
    ffor(i,1,q) {
        int l,r;
        cin>>l>>r;
        if(r-l+1>=n) cout<<ask(1,n)<<'\n';
        else {
            l=l%n+1;
            r=r%n+1;
            if(l<=r) cout<<ask(l,r)<<'\n';
            else cout<<max(ask(1,r),ask(l,n))<<'\n';
        }
    }
    return 0;
}