题面

题目描述

大圣在佛祖的手掌中。

我们假设佛祖的手掌是一个圆圈，圆圈的长为 $n$，逆时针记为：$0, 1, 2, \cdots, n - 1$，而大圣每次飞的距离为 $d$。现在大圣所在的位置记为 $x$，而大圣想去的地方在 $y$。要你告诉大圣至少要飞多少次才能到达目的地。

输入格式

有多组测试数据。

第一行是一个正整数 $T$，表示测试数据的组数。

每组测试数据包括一行， $4$ 个非负整数，分别为如来手掌圆圈的长度 $n$，筋斗所能飞的距离 $d$，大圣的初始位置 $x$ 和大圣想去的地方 $y$。

注意孙悟空的筋斗云只沿着逆时针方向翻。

输出格式

对于每组测试数据，输出一行，给出大圣最少要翻多少个筋斗云才能到达目的地。如果无论翻多少个筋斗云也不能到达，输出 $\texttt{Impossible}$。

样例

输入样例 #1

2
3 2 0 2
3 2 0 1

输出样例 #1

1
2

数据范围与提示

对于 $100 \%$ 的数据，$2 < n \le 10 ^ 9, 0 < d < n, 0 \le x, y, < n$。

My Solution

设答案是 $s$，则有

$$x + ds \equiv y \pmod n \\ s \equiv (y - x) \cdot d ^ {-1} \pmod n$$

当且仅当 $d ^ {-1}$ 不存在，即 $d$ 与 $n$ 不互质时无解。

代码：

#include <iostream>
#include <algorithm>

bool coprime(int a, int b) { return (std::__gcd(a, b) == 1); }

std::pair<int, int> exgcd(int a, int b)
{
    if (a % b == 0)
        return {0, 1};
    else
    {
        int x = exgcd(b, a % b).first;
        int y = exgcd(b, a % b).second;
        return {y, x - a / b * y};
    }
}

int inv(int a, int p) { return (0LL + exgcd(a, p).first + p) % p; }

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--)
    {
        int n, d, x, y;
        std::cin >> n >> d >> x >> y;
        if (x == y)
            std::cout << 0 << "\n";
        else if (!coprime(d, n))
            std::cout << "Impossible" << "\n";
        else
            std::cout << ((0LL + y - x + n) * inv(d, n) % n) << "\n";
    }

    return 0;
}

WA 求调。