acwing 1299.五指山（扩展欧几里得算法）

本文主要是介绍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

扩展欧几里得算法

欧几里得算法：可以求出两个数的最大公约数d 即(a, b) = d.
裴蜀定理 ------- 扩展欧几里得算法
指对于任意正整数对(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-k*a’;
我们来证明一下：
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));

#include<iostream>

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

int main()
{
	int T;
	cin >> T;
	while(T --)
	{
		ll n, d, x, y, a, b;// an + bd = gcd
		cin >> n >> d >> x >> y;
		
		int gcd = exgcd(n, d, a, b);
		if((y - x) % gcd) cout << "Impossible" << endl;//若gcd不能整除y-x,则无解
		else
		{
			b *= (y - x) / gcd;
			n /= gcd;
			cout << (b % n + n) % n << endl;//保证结果为正数
		}
	}
	return 0;
}

这篇关于acwing 1299.五指山（扩展欧几里得算法）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！