「一本通 6.4 练习 2」五指山

形式化题目

给定长度为 $n$ 的环，位置编号 $0,1,\dots,n-1$ 逆时针递增。初始位于 $x$ ，每次操作把位置加 $d$ 后对 $n$ 取模（只能沿逆时针方向跳，不能反向）。

求最小的非负整数 $k$ ，使得

(x + k\,d) \bmod n = y;

若不存在这样的

k

，输出 Impossible。

输入含 $T$ 组询问，每组给出 $n, d, x, y$ ，其中 $2 < n < 10^9$ ， $0 < d < n$ ， $0 \le x, y < n$ 。

样例 $n=3, d=2$ 时从 $0$ 出发的轨迹（位置按跳跃次数排列）：

$k$	0	1	2	3	…
位置	0	2	1	0	周期 3

可见第 1 次到 $2$ ，第 2 次到 $1$ ，与样例输出 1、2 一致。

正解

思路

设跳了 $k$ 次，因为每跳一次位置就增加 $d$ 并对 $n$ 取模，所以落点是 $(x + k\,d) \bmod n$ 。要求它等于 $y$ ，移项即得一元线性同余方程

k\,d \equiv y - x \pmod n. \tag{1}

于是问题从“模拟跳跃”变成了“解一个同余方程”，答案就是 (1) 的最小非负整数解。

第一步：判断有没有解。 记 $g = \gcd(d, n)$ 。由于 $kd$ 一定是 $g$ 的倍数， $kd \bmod n$ 也只能取到 $g$ 的倍数，所以由裴蜀定理，方程 (1) 有整数解当且仅当

g \mid (y - x).

若不整除，大圣的落脚点是一串永远踩不到 $y$ 的位置，输出 Impossible。

第二步：约简到系数可逆。 当 $g \mid (y-x)$ 时，把 (1) 的两侧与模数同时除以 $g$ ：

\frac{d}{g}\,k \equiv \frac{y-x}{g} \pmod{m},\qquad m = \frac{n}{g}. \tag{2}

此时 $\gcd\!\left(\frac{d}{g}, m\right) = 1$ ，系数在模 $m$ 下可逆，且 (2) 与 (1) 同解。

第三步：取最小非负解。 两边乘上逆元：

k \equiv \frac{y-x}{g} \cdot \left(\frac{d}{g}\right)^{-1} \pmod m .

方程的全部整数解是 $k_0 + t\,m$ （ $t \in \mathbb{Z}$ ， $k_0$ 为最小非负剩余）。跳跃次数必须非负： $t \ge 0$ 时解不小于 $k_0$ ， $t \le -1$ 时解至多为 $k_0 - m < 0$ 。所以 $k_0$ 就是最少的跳跃次数。

Python 中这一串推导可以合成为一个表达式：gcd(d, n) 给出 $g$ ，(y - x) % g 做整除判定， pow(d // g, -1, m) 直接给出模逆元（内建实现同样是扩展欧几里得，复杂度 $O(\log m)$ ）。不必手写 exgcd 迭代，也不必特判负数——Python 的 % 对负数返回非负余数，自动把结果调进 $[0, m)$ 。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 23:32
# update_at: 2026-09-30 23:32

import sys
from math import gcd

IMPOSSIBLE = "Impossible"  # 无解时的输出，单独命名避免散落在分支里


def min_jumps(n: int, d: int, x: int, y: int) -> int | None:
    """连跳 d 步首次落到 y 的最少次数；永远到不了则返回 None。

    跳 k 次后的位置是 (x + k*d) mod n，所以要求 k*d ≡ y-x (mod n)。
    设 g = gcd(d, n)：同余方程有解的充要条件是 g | (y-x)；
    否则两边同除以 g，得模 m = n/g 下唯一的同余类，
    乘上 d/g 的模逆元再对 m 取模，就是最小的非负跳跃次数。
    """
    g = gcd(d, n)
    if (y - x) % g:
        return None                                   # 差值不是 g 的倍数，无整数解
    m = n // g                                        # 约简后的模数，也是解的周期
    return (y - x) // g % m * pow(d // g, -1, m) % m   # pow(a, -1, m) 即 a 的模逆元


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)                                    # 测试数据组数

    for _ in range(T):
        n, d, x, y = next(data), next(data), next(data), next(data)
        jumps = min_jumps(n, d, x, y)
        out.append(IMPOSSIBLE if jumps is None else str(jumps))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 23:56
 * update_at: 2026-10-05 23:56
 */

// 题意：佛祖手掌是长为 n 的圆圈，大圣每次逆时针飞 d，问从 x 到 y 最少翻几个筋斗。
// 思路：跳 k 次后位置是 (x + k*d) mod n，解线性同余方程 k*d ≡ y-x (mod n)。
//       设 g = gcd(d, n)：g 不整除 (y-x) 时无解；否则两边除以 g，在模 m = n/g 下
//       用扩展欧几里得求 (d/g) 的逆元，得到最小非负解 k0，即答案。

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

ll n, d, x, y; // 每组询问的手掌长度 n、每次飞行距离 d、起点 x、终点 y

// 辗转相除求最大公约数
ll mygcd(ll a, ll b) {
    while (b != 0) {
        ll r = a % b;
        a = b;
        b = r;
    }
    return a;
}

// 扩展欧几里得：求 gcd(a, b)，并求出 a*x + b*y = gcd 的一组整数解
ll exgcd(ll a, ll b, ll &px, ll &py) {
    if (b == 0) {
        px = 1;
        py = 0;
        return a;
    }
    ll gx = 0, gy = 0;
    ll g = exgcd(b, a % b, gx, gy); // 先解子问题 b*x + (a%b)*y = g
    px = gy;                        // 回代：a%b = a - (a/b)*b
    py = gx - (a / b) * gy;
    return g;
}

// 解方程 k*d ≡ y-x (mod n)，返回最小非负解；无解返回 -1
ll solve_query() {
    ll g = mygcd(d, n);
    ll diff = ((y - x) % n + n) % n; // 差值先调成非负，方便整除判定
    if (diff % g != 0) {
        return -1; // g 不整除差值，永远到不了 y
    }
    ll m = n / g; // 约简后的模数，也是解的周期
    ll p = 0, q = 0;
    exgcd(d / g, m, p, q);          // 此时 gcd(d/g, m) = 1，逆元存在
    ll inv = ((p % m) + m) % m;     // 把逆元调成 [0, m) 内的最小非负剩余
    ll k = (diff / g % m) * inv % m; // 乘上逆元取模，k0 就是最少跳跃次数
    return k;
}

int main() {
    int T;
    if (scanf("%d", &T) != 1) {
        return 0;
    }
    while (T--) {
        scanf("%lld %lld %lld %lld", &n, &d, &x, &y);
        ll ans = solve_query();
        if (ans == -1) {
            printf("Impossible\n");
        } else {
            printf("%lld\n", ans);
        }
    }
    return 0;
}

复杂度

时间复杂度： $O(T \log n)$ 。每组数据一次 gcd 加一次模逆元，各为 $O(\log n)$ ，其余为 $O(1)$ 算术。
空间复杂度： $O(1)$ 额外空间（不含读入缓冲），与 $n$ 无关。

总结

题目把「圆环上单向等步长行走」抽象成一个同余方程 $kd \equiv y-x \pmod n$ 。 $\gcd(d,n)$ 决定可达性，约去公因子后系数可逆，模逆元直接给出唯一的最小非负解。核心结论是：答案只可能落在 $[0,\ n/\gcd(d,n))$ 内，一步模拟都不需要， $n$ 到 $10^9$ 也能瞬间出解。

图示解析

下图给出每组询问的判定与求解流程，重点看两条分支：不可达分支在 $\gcd$ 判定处直接结束，可达分支的答案由模 $m = n/g$ 的逆元运算一次性给出。

flowchart TD
    Start[读入 n d x y] --> G[g = gcd d n]
    G --> Div{g 整除 y - x ?}
    Div -- 否 --> Imp[输出 Impossible]
    Div -- 是 --> M[m = n / g]
    M --> Inv["求 d/g 在模 m 下的逆元"]
    Inv --> Sol["k0 = (y-x)/g * inv mod m"]
    Sol --> Ans[输出 k0]

流程中唯一的“复杂”运算是模逆元；它对应 (2) 式两侧同乘逆元这一步。 $m$ 既是模数也是解的周期，所以 k0 一旦求出就是最终答案，无需再回代验证。