ARC166E 题解

· · 题解

Problem Link

题目大意

数据范围：$T\le 2\times 10^5,n,a,b\le 10^6$。

思路分析

很显然把可以把原限制改成 n_a-n_b\le n。

那么很自然的贪心想法就是取 L\bmod a=1,R\bmod a=-1，那么 L=ua+1,R=va-1。

那么 n_a-n_b=(v-u-1)-\left(\left\lfloor\dfrac{va-1}b\right\rfloor-\left\lfloor\dfrac{ua}b\right\rfloor\right)，枚举 k=v-u，那么我们肯定想令后一部分尽可能大。

设 r=ua\bmod b，后一部分等于 \dfrac{va-1-(r+ka-1)\bmod b}b-\dfrac{ua-r}b=\dfrac{ka-1+(r-(r+ka-1)\bmod b)}{b}。

那么 r-(r+ka-1)\bmod b 在 r<b-(ka-1)\bmod b 时是 -(ka-1)\bmod b，否则是 b-(ka-1)\bmod b。

我们显然要让 r\ge b-(ka-1)\bmod b，但是注意 r=ua\bmod b，因此 r 最大值是 b-\gcd(a,b)。

此时原式取得 n_a-n_b=k-\left\lfloor\dfrac{ka-1}b\right\rfloor-[\gcd(a,b)\le (ka-1)\bmod b]。

显然这个式子具有单调性，可以直接二分。

求出 k 之后，如果 \gcd(a,b)>(ka-1)\bmod b 那么直接取 u=0 即可，否则我们要求最小的 u 使得 ua\bmod b\ge b-(ka-1)\bmod b。

那么我们可以看成这样一个问题，求 L\le xa\bmod p\le R 的最小自然数解：

首先如果 l=0 直接解决。

其次如果 [l,r] 中有 a 倍数，即 a\left\lceil \dfrac la\right\rceil\le r 那么 x_{\min}=\left\lceil \dfrac la\right\rceil。

否则设 k=\left\lfloor\dfrac{xa}p\right\rfloor，我们只需最小化 k，此时 x\ge \left\lfloor\dfrac{kp+l}a\right\rfloor。

那么 l\le ax-kp\le r 可以推出ax-r\le kp\le ax-l，进一步得到 (-r)\bmod a\le kp\bmod a\le (-l)\bmod a，可以递归处理。

注意到每次递归都会使得 (a,p)\gets (p\bmod a,a)，因此复杂度同辗转相除法。

时间复杂度 \mathcal O(T\log V)。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e12;
ll solve(ll l,ll r,ll a,ll p) { //ax mod p in [l,r]
    if(!l) return 0;
    if((l+a-1)/a*a<=r) return (l+a-1)/a;
    // l <= ax-kp <= r
    // x >= (kp+l)/a
    // -r%a <= pk%a <= -l%a
    ll k=solve((a-r%a)%a,(a-l%a)%a,p%a,a);
    return (k*p+l+a-1)/a;
}
signed main() {
    int T;
    scanf("%d",&T);
    for(ll a,b,n;T--;) {
        scanf("%lld%lld%lld",&n,&a,&b);
        ll L=0,R=inf,g=0,d=__gcd(a,b);
        while(L<=R) {
            ll mid=(L+R)>>1;
            if((mid-1)-(a*mid-1)/b-(d<=(a*mid-1)%b)<=n) g=mid,L=mid+1;
            else R=mid-1;
        }
        ll k=(d<=(a*g-1)%b)?solve((b-(a*g-1)%b)%b,b-1,a,b):0;
        printf("%lld %lld\n",a*k+1,a*(k+g)-1);
    }
    return 0;
}