题解：P8249 模法问题

· · 题解

P8249 模法问题 题解

前言

ST表不错的练习题，感觉有点考验注意力。

题目大意

给定两个正整数 a,b，进行 q 次询问，每次询问区间 [l,r] 中 \max\{(i \bmod a)+(i \bmod b)\} 的值。

解题思路

关键观察

算法设计

  1. 预处理 L = \operatorname{lcm}(a,b)。
  2. 计算 f(i) 在 i=0,1,\dots,L-1 的值。
  3. 构建：
    • 前缀最大值数组 pre。
    • 后缀最大值数组 suf。
    • ST表用于区间最值查询。
  4. 对于每个询问 [l,r]：
    • 若区间长度 \ge L，直接返回全局最大值。
    • 否则，将区间映射到 [0, L-1] 内：
      • 若 l \bmod L \le r \bmod L，使用ST表查询区间最大值。
      • 否则，ans = \max(后缀[l \bmod L], 前缀[r \bmod L])。

时间复杂度

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int a,b,L,q,mx;
int v[N],pre[N],suf[N],st[20][N],lg[N];
inline int lcm(int x,int y){return x/__gcd(x,y)*y;}
void build()
{
    lg[1]=0;
    for(int i=2;i<=L;i++) lg[i]=lg[i>>1]+1;
    for(int i=0;i<L;i++) st[0][i]=v[i];
    for(int j=1;(1<<j)<=L;j++)
        for(int i=0;i+(1<<j)-1<L;i++) st[j][i]=max(st[j-1][i],st[j-1][i+(1<<(j-1))]);
}
int query(int l,int r)
{
    int k=lg[r-l+1];
    return max(st[k][l],st[k][r-(1<<k)+1]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>a>>b;
    L=lcm(a,b);
    for(int i=0;i<L;i++)
    {
        v[i]=i%a+i%b;
        mx=max(mx,v[i]);
        pre[i]=mx;
    }
    suf[L-1]=v[L-1];
    for(int i=L-2;i>=0;i--) suf[i]=max(suf[i+1],v[i]);
    build();
    cin>>q;
    while(q--)
    {
        ll l,r;
        cin>>l>>r;
        if(r-l+1>=L)
        {
            cout<<pre[L-1]<<'\n';
            continue;
        }
        int lmod=l%L,rmod=r%L;
        if(lmod<=rmod)
        {
            cout<<query(lmod,rmod)<<'\n';
        }
        else
        {
            int ans=max(suf[lmod],pre[rmod]);
            cout<<ans<<'\n';
        }
    }
    return 0;
}