P8249 模法问题题解

jgvccc · 2022-04-02 23:23:12 · 题解

题目传送门

显然，这道题不能用暴力做，因为仅仅计算单个的问题，就会达到 10^9 的复杂度。

这个时候就需要考虑其他方法了。

因为这道题求的是余数的和，所以 最理想 的情况答案应为 (a-1)+(b-1) （如下图所示）。但是这种情况的出现当且仅当 (a,b] 区间内存在 a,b 的公倍数的时候。

我们可以新建一个变量 t 存储 a 与 b 的最小公倍数，然后对于每个询问，存储 l \div t 和 r \div t 的值。如果这两个值不相等，则可判断为上文中提及的情况，条件如下。

if(l \ t != r \ t)

不过，当 l \div t = r \div t 时，这种方法就不奏效了，因为区间几乎不可能出现我们所期望的值了（如下图）。

~~因为本蒟蒻不会倍增算法，所以~~ 我们可以另辟蹊径。通过观察可以发现，在单独对一个数取余的两个序列中，会出现余数为 0 的情况。而 0 前面的数字则是这一行可能出现的最大数字。反过来推，可以得到： 如果一个数字的右边是0，那么它一定是该行最大的。如果不是0，那么它一定不是该行最大的。

所以如果有一列的数右边都不是 0 ，那么可以直接排除这一列。所以我们 只需要扫一遍所有0左边的结果即可 ，这就大大减少了计算量，省去了很多时间复杂度。这还没完，千万不要忘记最右边的数也有可能是最大值，所以 最后一个数r也要扫 。

总结一下：如果区间内存在最理想情况，直接输出。如果不存在，扫描一遍所有的 0 左边的结果和 r 。

上代码：

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

int a,b,q,l,r,t,minn,maxn,ans;
int gcd(int a,int b)//最大公约数
{
    if(a % b == 0) return b;
    else return gcd(b,a % b);
}

int calc(int x)//计算结果
{
    return x % a + x % b;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    cin>>a>>b;
    t = gcd(a,b);
    t = a * b / t;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        cin>>l>>r;
        minn = l / t;
        maxn = r / t;
        ans = 0;
        if(minn != maxn) cout<<calc(maxn*t-1)<<endl;//最理想情况
        else
        {
            ans = calc(r);//千万别忘了扫这个位置
            for(int i = r/a*a-1;i>=l;i-=a) ans = max(ans,calc(i));//扫一遍除以第一个数余0的位置的左边并取最大值
            for(int i = r/b*b-1;i>=l;i-=b) ans = max(ans,calc(i));//扫一遍除以第二个数余0的位置的左边并取最大值
            cout<<ans<<endl;
        }
    }
    return 0;
}

P8249 模法问题 题解

P8249 模法问题题解