AcWing 1299. 五指山

大圣在佛祖的手掌中。
我们假设佛祖的手掌是一个圆圈，圆圈的长为 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

题意：在一个长度为n且逆时针编号从0~n-1的环中，每次逆时针移动距离为d，计算至少多少次移动从位置x至位置y

解题前首先要了解两个部分

裴蜀定理

如果a，b是整数，则必然存在整数x，y（多解）使得ax + by = gcd(a,b)

其中涉及一个推论，在已经求出一组解x0,y0时，可以通过这组解表达出这个等式的任意解

x = x0 + k * b/d
y = y0 - k * a/d

关于裴蜀定理的证明方法有很多，基本一个地方一个证法，就不再赘述

对于如何求出对于（a，b）的系数x，y，这里要用到一种算法

扩展欧几里得算法

欧几里得算法比较常见，即是辗转相除法

gcd(a,b) = gcd(b,a mod b)

static int gcd(int a,int b) {//不必在意大小
		if(b==0) 
			return a;
		return gcd(b,a%b);
	}

在常规gcd中进行修改即可在获得a，b的最大公因数的同时获得系数x，y即裴蜀定理

首先考虑在常规欧几里得算法代码中，由于使用递归，在计算gcd（a,b）时，我们可以先获得下一层gcd（b,a mod b）的数据，即在计算a * x+b * y=gcd（a,b）中的x，y值时，我们已经求出了下一状态b * x1+(a%b) * y1=gcd(b,a%b)中的x1，y1的值

那么梳理两式之间的关系，尝试用x1，y1来表达出x，y
首先已知

a%b=a-(a/b)*b

将其带入原式

b * x1 + (a%b) * y1 = gcd
b * x1 + a * y1 – (a/b) * b * y1 = gcd
a * y1 + b * (x1 – a/b * y1) = gcd

至此可以发现

x = y1
y = x1 – a/b * y1

由于递归至b=0时结束，此时式为a1+b0=gcd，可得到最底层的xn=1，yn=0，在这组数据的基础上递归回溯，不断更新至初始a，b值，此时的x，y即为所求

由于java中不支持指针方式传参修改变量，因此定义了全局变量来实现

static int x,y;
	static int exgcd(int a,int b) {
		if(b==0) {
			x=1;
			y=0;
			return a;
		}
		int ans=exgcd(b,a%b);//先进行递归获得x1y1后再更新xy
		int t=x;
		x=y;
		y=t-a/b*y;
		return ans;
	}

回到题目，假设翻了b次后到达y点，此时已经绕了a圈，可以整合出式子

x+bd=y+an
-an+bd=y-x

在n,d,x,y都是常数的情况下，可见题目实际就是裴蜀定理的应用，如果y-x=gcd（n,d），则说明等式可以成立，否则无解

在使用扩展欧几里得算法求出一个解b0后，由于题目要求的是b的最小值，因此根据推论，b的最小值即是b0 mod n/(n-d)

代码如下

import java.io.*;
import java.util.*;


public class Main {
	static Scanner tab = new Scanner(System.in);
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int N = 50010;

	static long x,y;
	
	static long exgcd(long a,long b) {
		if(b==0) {
			x=1;
			y=0;
			return a;
		}
		long ans=exgcd(b,a%b);
		long t=x;
		x=y;
		y=t-a/b*y;
		return ans;
	}
	
	public static void main(String[] args) throws IOException {
		int T=tab.nextInt();
		while(T-->0) {
			long n=tab.nextLong();
			long d=tab.nextLong();
			long a=tab.nextLong();
			long b=tab.nextLong();
			
			long gcd=exgcd(n,d);
			if((b-a)%gcd!=0)
				System.out.println("Impossible");
			else {
				y*=(b-a)/gcd;
				n/=gcd;
				System.out.println((y%n+n)%n);
			}
		}
	}
}