思路与算法

把位置差规范化为delta=(y-x+n)%n。飞t次后的位置为(x+td)%n，因此需要解dt与delta模n同余。令g=gcd(d,n)，只有g整除delta时才有解；约去g后，d/g在模n/g下可逆。用扩展欧几里得取得逆元，乘delta/g并对n/g取模，得到最小非负次数。

正确性说明

一次同余方程有解当且仅当gcd(d,n)整除右端；必要性来自g整除d与n，充分性来自扩展欧几里得恒等式。约去g后两个模数因子互质，所以逆元存在且解在模n/g意义下唯一。所有非负解都相差n/g，规范化到0至n/g-1的解最小。若起点等于终点，delta为0，正确答案为0。无解时按题目输出Impossible。

复杂度

每组扩展欧几里得O(log n)，其余计算O(1)，递归栈O(log n)。首行组数用文本读入，随后流式处理合法输入中的全部四元组，避免把未给上界的组数先截断为int；另计该文本的O(len(T))读入和存储。初始化每组变量O(1)。n<10^9，归一化后的乘积小于10^18，参考公共求解器使用无符号64位。

易错点

只能沿指定方向翻，不能把距离取绝对值。必须先判断g整除delta，再求约分后的逆元；有解不等于d与n互质。x=y输出0。Impossible大小写固定。独立答案用Python模逆，并对600个小圆圈逐步模拟验证。

参考代码（C++11）

#include <iostream>
#include <string>
using namespace std;
long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    long long u, v;
    long long g = exgcd(b, a % b, u, v);
    x = v;
    y = u - (a / b) * v;
    return g;
}
long long solve(long long c, long long delta, long long mod) {
    long long x, y, g = exgcd(c, mod, x, y);
    if (delta % g)
        return -1;
    long long reduced = mod / g;
    if (reduced == 1)
        return 0;
    x = (x % reduced + reduced) % reduced;
    unsigned long long product = (unsigned long long)x * (unsigned long long)(delta / g);
    return product % (unsigned long long)reduced;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string groups;
    cin >> groups;
    long long n, d, x, y;
    while (cin >> n >> d >> x >> y) {
        long long answer = solve(d, (y - x + n) % n, n);
        if (answer < 0)
            cout << "Impossible\n";
        else
            cout << answer << '\n';
    }
}