题目描述

大圣在佛祖的手掌中。

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

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

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

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

输入格式

有多组测试数据。

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

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

输出格式

对于每组测试数据，输出一行，给出大圣最少要翻多少个筋斗云才能到达目的地。

如果无论翻多少个筋斗云也不能到达，输出 Impossible。

数据范围

2<n<109,
0<d<n,
0≤x,y<n

输入样例：

2
3 2 0 2
3 2 0 1

输出样例：

1
2

扩展欧几里得算法

欧几里得算法：可以求出两个数的最大公约数d  即(a, b) = d.

裴蜀定理      -------   扩展欧几里得算法
可以求出最大公约数d，且可以求出 ax + by = d 的系数 
(a, b)
ax + by = d
a' = a / d
b' = b / d

//任意一组解
x = x0 + kb'
y = y0 + ka'

证明过程：
由
ax0 + by0 = d
ax' + by' = d

推出:
a(x' - x0) = b(y0 - y')
a'(x' - x0) = b'(y0 - y')

=> b'|a'(x' - x0)
由于a' 与 b' 互质
=> b'|(x' - x0)


=> x' - x0 = kb'

(a, b) = (b, a % b)

假设递归时求出了a 和 b
by + (a mod b)x = d
= by + (a - a/b * b)*x     //因为递归的时候b与a互换了位置,同时y与x也应互换位置
= ax + (y - a/b * x)*b = d

=> x' = x
=> y' = y - a / b * x

解题思路：

由题目可以抽象出数学模型如下：

x + pd = y(mod n)
x + pd = y + qn
-qn + pd = y - x 即形式为qn + pd = y - x    ------ 方程1

由于n, d, y, x都为常数,以及q, p 均为变量我们很容易联想到扩展欧几里得算法 ax + by = d  ------ 方程2
但我们题目要求的和扩展欧几里得算法右边的有些不同,扩展欧几里得算法右边的为最大公约数,我们题目给出的y - x未必
是n和d的最大公约数,当思考后我们发现,如果d不能整除y - x则无解.我们可以先用扩展欧几里得算法求出n和d的最大公约
数,然后将方程2乘以(y - x) / d 即可转化为方程1,我们观察题目发现题目要求的是最小的p值,那如何求呢？
由扩展欧几里得解得结论我们可以得到： p = p0 + kn/d,p最小为p0,p0即是我们题目要求的最小值

C++ 代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

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);//d为a和b的最大公约数
    y -= a / b * x;

    return d;
}

int main(){
    int T;
    scanf("%d", &T);

    while(T --){
        LL n, d, x, y, p, q;//qn + pd = gcd
        scanf("%lld%lld%lld%lld", &n, &d, &x, &y);
        LL gcd = exgcd(n, d, q, p);
        if((y - x) % gcd) printf("Impossible\n");//若gcd不能整除y-x,则无解
        else{
            p *= (y - x) / gcd;
            n /= gcd;
            printf("%lld\n", (p % n + n) % n);//保证结果为正数
        }
    }

    return 0;
}