题目描述

大圣在佛祖的手掌中。

我们假设佛祖的手掌是一个圆圈，圆圈的长为 n，逆时针记为：0,1,2,…,n−1，而大圣每次飞的距离为 d。

现在大圣所在的位置记为 x，而大圣想去的地方在 y。

要你告诉大圣至少要飞多少次才能到达目的地。

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

输入格式
有多组测试数据。

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

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

样例

输入：
2
3 2 0 2
3 2 0 1
输出：
1
2

首先，先说一下扩展欧几里得定理：指对于任意正整数对(a,b)，一定存在非零整数x和y，使得 ax+by=gcd(a,b)；
我们来分情况讨论一下扩展欧几里得定理：
(1)当b = 0时，a和b的最大公约数为a.则x = 1;
(2)当b ≠ 0时，by+(a mod b)x = gcd(a,b)
->by+(a - a/b * b)x = gcd(a,b)
->ax+b(y - a/b * x) = gcd(a,b)
即当我们用扩展欧几里得定理求x和y时，欧几里得定理每递归一次x不用变,y->y-a/b * x即可
如果我们求出x和y的一对，我们记为x0和y0
那么其他的x和y可以通过x0，y0表示:
令a’=a/gcd(a,b) , b’=b/gcd(a,b);

那么其他的x和y可以表示为：x=x0+kb’,y=y0-ka’;
我们来证明一下：
ax0+by0 = gcd(a,b)
ax+by = gcd(a,b)
如果x0比x小，那么y0就应该比y大，这样加起来的结果才可能相同
所以，a(x-x0) = b(y0-y);
两边同时除以一个gcd(a,b)
得到：a’(x-x0) = b’(y0-y)
那么b’就应该能整除a’(x-x0)，又因为a’和b’互质，所以b’应该能整除(x-x0)

所以(x-x0) = kb’
则 x = x0+kb’
y = y0-ka’
这里的k可正可负

回到这道题，这题的题意是让我们求x+bd = y+an ,整理得：-an+bd = y-x
但是我们得扩展欧几里得定理只能求 -an+bd = gcd(n,d)中的a和b，但是很容易看出y-x应该为gcd(n,d)的整数倍
否则无解。
因此我们只需要判断y-x是否为gcd(n,d)的整数倍就能判断是否有解了。
若有解我们利用扩展欧几里得定理就可以求得-an+bd = gcd(n,d)中的a和b，然后将a和b扩大 (y-x)/gcd(n,d)倍
就可以得到一组a0和b0，因为之前我们证过了获得一组解后其他解就可以表示出来了，我们只需要求一下所有解中的最小值就可以了（注意我们的b只能是正数，你总不能让大圣反着翻吧）
即：
求一下b = b0+k*(n/gcd(n,d))的最小值即可
minb = b0%(n/gcd(n,d));

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstdio>
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;
    }
    int d = exgcd(b,a%b,y,x);
    y -= a/b*x;
    return d;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        LL n,d,x,y,a,b;
        scanf("%lld%lld%lld%lld",&n,&d,&x,&y);

        int gcd = exgcd(n,d,a,b);
        if((y-x)%gcd){
            printf("Impossible\n");
        }else{
            b*=(y-x)/gcd;
            n/=gcd;
            printf("%lld\n",(b%n+n)%n);
        }
    }
    return 0;
}