ABC334B 题解

Xwink · 2024-12-29 17:17:21 · 题解

忽然想到的奇妙做法。

该做法的核心在于平移区间。

我们首先令 l_1=l-A,r_1=r-A，这样相对于 l_1,r_1 而言圣诞树就分布在 kM 的位置上。

不过此时 l_1 仍然有可能是负数，不便于我们处理。这时我们再将 l_1,r_1 整体加上 (-\frac{l}{M}+1)\times M，得到 l_2,r_2，容易发现它们一定都是正数，且此时问题与原问题等价。

答案即为 \lfloor\frac{r_2}{M}\rfloor-\lfloor\frac{l_2-1}{M}\rfloor。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll a,m,l,r;
    cin>>a>>m>>l>>r;
    l-=a,r-=a;
    if(l<0){
        ll d=(-l)/m+1;
        l+=d*m,r+=d*m;
    }
    printf("%lld",r/m-(l-1)/m);
    return 0;
}