信息学奥赛一本通1638：五指山

url: https://ybt.ssoier.cn/problem_show.php?pid=1638

tag:
裴蜀定理，拓展欧几里得算法，数论

思路：
根据题意可以得出，y - x = b d mod n ⇒ b d - a n = y - x。所以可以先求出n与d的最大公约数，如果y - x 不能整除，说明不能到达，如果可以整除再求最小的b。用拓展欧几里得算法可以求出 x n + y d = (n,d) 的一组解，然后令该式两边同乘 （y - x）/ （n，d）可以将该式变为b d - a * n = y - x。最后求最小的d就是让其取模n / gcd的正余数。
代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main()
{
    int T;
    cin >> T;
    while (T --)
    {
        LL n, d, x, y, a, b;
        scanf("%lld%lld%lld%lld", &n, &d, &x, &y);
        LL gcd = exgcd(n, d, a, b);
        if ((y - x) % gcd) cout << "Impossible\n";
        else
        {
            b *= (y - x) / gcd;
            n /= gcd;
            printf("%lld\n", (b % n + n) % n);
        }
    }
    return 0;
}