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;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

2 条评论

scnucjh · 2020年5月9日 5:39 下午

这个式子的 ?? 可以拆开并且移项到 −? 和 −? 项中,因此整个式子可以对 ? 取模:

为什么可以对 D 取模, 这里还是很不理解

    Remmina · 2020年5月11日 11:48 下午

    好吧我确实是不记得了,想了很久也不记得当时是怎么想的了。
    也许式子写成 $L \leq Dx – My \leq R$ 会更容易理解,因为 $x, y$ 之间是独立的。
    其实这里若存在答案,那 $y$ 必然等于 $\lfloor \frac {Dx} {M} \rfloor$。

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注