拓展欧几里得

2024-02-10 19:43:40

拓展欧几里得：

ll exgcd(ll a, ll b, ll &x, ll &y)
{
	if(b == 0)
	{
		x = 1, y = 0;
		return a;
	}
	ll ans = exgcd(b, a%b, x, y);
	ll tmp = x;
	x = y;
	y = tmp - a / b * y;
	return ans; //返回的还是gcd(a, b) 但此过程中改变了x，y的值
}

对于方程\(ax+by=gcd(a,b)\),我们可以通过exgcd来求出一组{x, y}的特解

同时我们可以推导出通解：

已知\(ax_0+by_0=ax+by=c\),

那么\(a(x-x_0)=-b(y-y0)\)

我们对等号两边同除\(gcd(a,b)\)

则\(\frac{a}{gcd(a,b)}(x-x_0)=-\frac{b}{gcd(a,b)}(y-y_0)\)

我们知道\(gcd(\frac{a}{gcd(a,b)},\frac{b}{gcd(a,b)}) = 1\)

因此\(\frac{b}{gcd(a,b)}|(x-x_0)\)

可以写出通解\(x=x_0+t\frac{b}{gcd(a,b)}\)

而对于\(x\)的最小解，则是\(x_{min}=x(mod\;\frac{b}{gcd(a,b)})\)

代码示例：

xmin = (x *(c / gcd(a, b)) % (b / gcd(a, b) + (b / gcd(a, b))) % (b / gcd(a, b));

因为我们计算\(x\)是基于方程\(ax+by=c\)的情况，因此\(x\)需要\(*\frac{gcd(a, b)}{c}\), 相当于把等号右边的\(c\)变为\(gcd(a, b)\)

而\(+(b / gcd(a, b))\)是防止负数的情况

例：青蛙的约会Luogu P1516

题目描述

两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。

我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

输入格式

输入只包括一行5个整数x，y，m，n，L

其中0<x≠y < =2000000000，0 < m、n < =2000000000，0 < L < =2100000000。

输出格式

输出碰面所需要的天数，如果永远不可能碰面则输出一行"Impossible"。

输入输出样例

输入 #1

1 2 3 4 5

输出 #1

代码示例:

//#pragma comment(linker,   "/STACK:10240000000000,10240000000000")
//#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define For(i,a,b) for (int i=(a);i<=(b);++i)
#define Fod(i,b,a) for (int i=(b);i>=(a);--i)
#define mls multiset
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pob pop_back
#define itt iterator
#define lowbit(x) x & (-x)
#define clr(x) memset(x, 0, sizeof(x));

typedef long long ll;
typedef unsigned long long ull;
		
using namespace std;
const int MAXN = 0x7fffffff;
const int MOD = 1000000007;

ll sx, sy, m, n, l;
ll x, y;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
	if(b == 0)
	{
		x = 1, y = 0;
		return a;
	}
	ll ans = exgcd(b, a%b, x, y);
	ll tmp = x;
	x = y;
	y = tmp - a / b * y;
	return ans;
}

int main ()
{	
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> sx >> sy >> m >> n >> l;

	ll a, b, c;

	a = m - n, c = sy - sx, b = l;

	if(a < 0) a *= -1, c *= -1; //防止负数

	ll ans = exgcd(a, b, x, y);

	if(c % ans != 0) cout << "Impossible" << endl;

	else cout << ((x * (c / ans)) % (b / ans) + (b / ans)) % (b / ans) << endl;

	return 0;
}

码农公寓