扩展欧几里得定理

青蛙的约会

题目描述

两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

输入

输入只包括一行5个整数x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。

输出

输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行”Impossible”

样例输入

1 2 3 4 5

样例输出

解释

可以列出同余方程 (x + m * t) % l = (y + n * t) % l，即(x + m * t) = (y + n * t) + k * l。移项得(x - y) + t * (m - n) = k * l。仿照二元一次不定方程的形式ax + by = c，我们可以得到l * k + (n - m) * t = x - y。
根据输入的数据，我们知道l, m, n, x, y这五个数，并且可以求出(n - m)和(x - y)。我们将l, (n - m), (x - y)代入扩展欧几里得算法，得到k和t的一组解(x0 * (c / gcd(a, b)), y0 * (c / gcd(a, b)))。
方程无解的条件是c % gcd(a, b) != 0。如果满足方程无解的条件，输出”Impossible”。
否则，我们要求的是t的最小非负整数解。
t的公式可以通过(y0 + a / gcd(a, b)) % (a / gcd(a, b))得到。
(上述部分为了解释更清楚，和代码部分的字母有所不同。)

代码部分

#include<iostream>
#define int long long
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
	if (!b) {
		x=1,y=0;
		return a;
	}
	int d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
signed main()
{
	int x0,y0,m,n,l;
	cin>>x0>>y0>>m>>n>>l;
	int x,y;
	int r=exgcd(l,n-m,x,y);
	if ((x0-y0)%r!=0) cout<<"Impossible\n";
		else {
			int t=(y*(x0-y0)/r%(l/r)+l/r)%(l/r);
			cout<<t<<endl;
		}
	return 0;
}

exgcd

题目描述

给出一个等式ax + by = c,计算可能的解(x0, y0)使得|x0 + y0|的值最小。
如果有多组解，输出其中的一种；如果无解，输出-1。

输入

t组数据，每组数据1行，包含a,b,c。其中-1e9 <= a,b,c <= 1e9, 1 <= T <= 1e5。

输出

同题目描述

样例输入

4
1 2 3
1 -1 -2
5 7 3
2 4 -3

样例输出

1 1
0 2
2 -1
-1

Note

在第二组数据中,(-1,1)也是一组可行解。

解释

首先判断a = 0,或者b = 0的一些情况，然后将a, b, c跑一次扩展欧几里得算法，得到一组解。我们要求的是绝对值之和最小的一组解。我的方法是：首先将x为最小非负整数的情况求出来，然后算出此时的y；然后将x为最大非正整数的情况求出来，算出此时的y；将y为最小非负整数的情况求出来，算出此时的x，将y为最大非正整数的情况求出来，算出此时的y。将这几种情况比较，就能得到最终绝对值之和最小的解。
不得不说，这题我的代码较为冗余丑陋。

代码部分

#include<iostream>
#define int long long
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
	if (!b) {
		x=1,y=0;
		return a;
	}
	int d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
signed main()
{
	int t;
	cin>>t;
	while (t--) {
		int a,b,c;
		cin>>a>>b>>c;
		if (a==0&&b==0) {
			if (c==0) cout<<"0 0"<<endl;
				else cout<<-1<<endl;
			continue;
		}
		int x,y;
		int r=exgcd(a,b,x,y);
		if (c%r!=0) {
			cout<<-1<<endl;
			continue;
		}
		int x0=x*(c/r),y0=y*(c/r);
		pair<int,int> res;
		res.first=1e9+1,res.second=1e9+1;
		if (a==0||b==0) {
			cout<<x0<<' '<<y0<<endl;
			continue;
		}
		int xx,yy,k;
		xx=(x0+(b/r))%(b/r);
		k=(xx-x0)/(b/r);
		yy=y0-(a/r)*k;
		if (abs(xx)+abs(yy)<=abs(res.first)+abs(res.second)) {
			res.first=xx,res.second=yy;
		}
		xx-=(b/r);
		yy+=(a/r);
		if (abs(xx)+abs(yy)<=abs(res.first)+abs(res.second)) {
			res.first=xx,res.second=yy;
		}
		xx+=(b/r),xx+=(b/r);
		yy-=(a/r),yy-=(a/r);
		if (abs(xx)+abs(yy)<=abs(res.first)+abs(res.second)) {
			res.first=xx,res.second=yy;
		}
		yy=(y0+(a/r))%(a/r);
		k=(y0-yy)/(a/r);
		xx=x0+(b/r)*k;
		if (abs(xx)+abs(yy)<=abs(res.first)+abs(res.second)) {
			res.first=xx,res.second=yy;
		}
		xx+=(b/r);
		yy-=(a/r);
		if (abs(xx)+abs(yy)<=abs(res.first)+abs(res.second)) {
			res.first=xx,res.second=yy;
		}
		xx-=(b/r),xx-=(b/r);
		yy+=(a/r),yy+=(a/r);
		if (abs(xx)+abs(yy)<=abs(res.first)+abs(res.second)) {
			res.first=xx,res.second=yy;
		}
		cout<<res.first<<' '<<res.second<<endl;
	}
	return 0;
}