1. 题目

传送门=￣ω￣=

2. 题解

网上一篇题解都搜不到。。。

一份参考代码都没有

问题给出 $M, D, L, R$，求 $L \leq Dx \mod M \leq R$的最小正整数解，数据范围 $\leq 10 ^ 9$。

首先判断如果存在 $Dx \in [L, R],(Dx < M)$则直接返回答案。

否则说明走一圈（$M$）的路程之内是无法到达 $[L, R]$内的。

式子可以写成 $L \leq Dx – M \times \lfloor \frac {Dx} {M} \rfloor \leq R$

取反：

$-R \leq M \times \lfloor \frac {Dx} {M} \rfloor – Dx \leq -L$

这个式子的 $Dx$可以拆开并且移项到 $-R$和 $-L$项中，因此整个式子可以对 $D$取模：

$(-R \mod D) \leq (M \times \lfloor \frac {Dx} {M} \rfloor \mod D) \leq (-L \mod D)$

然后发现当前这个式子和最开始的 $L \leq Dx \mod M \leq R$形式是相同的，但是规模减小了，因此递归处理就可以得到 $\lfloor \frac {Dx} {M} \rfloor$的值，由此可以推算得到 $x$的值。

递归的形式和求 $gcd$是一样的，复杂度 $O(ln(n))$级别的

如果要感性理解的话呢就是我当前无法一圈内走完。

则设我需要走 $y$圈，每圈长度为 $M$

走完以后可以使我最后一次在原点（坐标 $0$，也可以认为是坐标 $M$）之前的位置变为 $-(My \mod D)$

到达 $-(My \mod D)$之后我再跳一步 $D$就到达原点的右边了

也就是我给当前这次从原点开始的跳跃提供了一个提前量——$My \mod D$

设我从 $-(My \mod D)$这个位置开始跳，要跳 $k$次才能到达 $[L, R]$内，则：

$L \leq Dk – (My \mod D) \leq R$

移项：

$L – Dk \leq – (My \mod D) \leq R – Dk$

这里 $k$可以随便取，所以你可以理解为把 $[L, R]$向左移动 $k$次，每次移动距离 $D$，使得坐标负半轴上的点 $- (My \mod D)$在区间内

然后把这个式子取反得到：

$(-R \mod D) \leq (My \mod D) \leq (-L \mod D)$

（因为 $k$随便取所以 $-Dk$可以直接替换成取模）

这里的式子和上面直接数学推导得到的式子是一样的，依然是递归求出 $y$即可

无解情况就是 $L > R$或者 $D = 0$

注意初始的时候 $R$要对 $M – 1$取 min

代码：

#include <cstdio>
#include <iostream>
#include <cctype>

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int Dfs(int m, int d, int l, int r)
{
    if (l > r || !d) return -1;
    if (1ll * r / d * d >= l) return (l - 1) / d + 1;
    int x = Dfs(d, m % d, ((-r) % d + d) % d, ((-l) % d + d) % d);
    if (x == -1) return -1;
    return (1ll * m * x + l - 1) / d + 1;
}

int T;

int main(int argc, char const* argv[])
{
    IN(T);
    while (T--)
    {
        int M, D, L, R, G;
        IN(M), IN(D), IN(L), IN(R), R = min(R, M - 1);
        printf("%d\n", Dfs(M, D, L, R));
    }
    return 0;
}