poj 1061 青蛙的约会 扩展欧几里得 最小正整数解

缘起

【1】中我们已经给出了欧几里得的模板——可以快速求出最大公约数. 但是扩展欧几里得算法不仅可以快速求出最大公约数，而且还可以求出ax+by=c这种（丢番图）方程的一组解（称之为特解）. 于是找一道题 poj 1061 青蛙的约会 来学习这种算法.

分析

题目是中文的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于
是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没
有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除
非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程
序来判断这两只青蛙是否能够碰面，会在什么时候碰面。 
我们把这两只青蛙分别叫做青蛙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

【样例输出】
4

【限制】
Time limit 1000 ms 
Memory limit 10000 kB

假设跳了K次相遇了，则有如下等式

1
2
3
4
5
x+Km=y+Kn+PL, 其中P是套圈的次数(可能P<0)
即
x-y = K(n-m)+PL
这样就转换为了一个形如
ax+by=c 的问题,其中c = x-y, a = n-m, b = L>0

所以我们考虑问题 ax+by=c 的所有解中（这种方程要么没有解，要么有无穷多解）x为最小的正整数的解.

我们分两步走.

Step1. 求出gcd(a,b)=d, 并且找到一组特解x0,y0满足 ax0+by0=d, 如果d不是c的因子，那么ax+by=c必然无解. 则本题结束. 如果有解

Step2. ax0+by0=d, 两边乘以c/d, 得到 a*(c/d)*x0+b*(c/d)*y0=c, 于是我们找到了一组ax+by=c的特解

(c/d*x0, c/d*y0)

那么我们的想法自然是——基于这组特解，给出ax+by=c的通解, 然后通过调整通解的系数找到满足条件的解.

而显然的，如果ax+by=c的特解为(x1,y1)的话, 则通解为 (x1+b1*t,y1-a1*t), t是整数, a1=a/d, b1=b/d, 所以可以通过调整t求出满足条件的解.

纵观上面的Step2, 其实Step2是给出算法了的. 关键在Step1, Step1是求出gcd之余还求出了ax+by=gcd(a,b)的一组特解（该组特解可以用于给出ax+by=c的一组特解，进而使用Step2的思路找到满足条件的解），我们把Step1的算法成为扩展欧几里得（因为在欧几里得算法的基础上求出了一组特解）

那么怎么求出ax+by=gcd(a,b)的一组特解呢? 想也不用想——就是在欧几里得的过程中干点事情——因为欧几里得的本质是(a,b)=(b,a%b)=gcd, 我们这样想，如果已经求出了

bx+(a%b)y = gcd 的一组特解(x,y)的话, 怎么求出ax+by=gcd的一组特解呢? 其实很简单

1
2
3
4
5
6
7
bx+(a%b)y = gcd
=>
bx+(a-a/b*b)*y = gcd
=>
ay+b(x-a/b*y)=gcd
所以(y,x-a/b*y) 就是ax+by=gcd的一组特解
所以我们完全可以把上述推导结果放进递归版的欧几里得算法中去
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL
typedef __int64 LL;

LL extgcd(LL a, LL b, LL &x, LL &y) // 扩展欧几里得, 求出 gcd(a,b)的同时, 找到 ax+by=gcd(a,b)的一组特解, 并且将这组特解存入(x,y)中去
{
	if (!b)
	{
		x = 1, y = 0; // ax+by = gcd(a,b)=a
		return a;
	}
	LL ans = extgcd(b,a%b, x,y),t; // 求出 bx+(a%b)y=gcd(a,b)的一组特解(x,y), 要从这组特解得到ax+by=c的一组特解
	t = x,x=y,y=t-a/b*y;
	return ans;
}


int main() 
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	LL x,y,m,n,L;
	scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&L);
	LL c = x-y, a = n-m, b = L;
	LL gcd = extgcd(a,b,x,y); // 得到 ax+by=gcd(a,b)的一组特解(x,y)
	if (c%gcd)
	{
		puts("Impossible");
	}
	else
	{
		x*=c/gcd, y*=c/gcd; // 得到 ax+by=c的一组特解(x,y)
		b/=gcd; // 即ax+by=c的通解中的b1, 注意, 因为gcd是a,b的最大公约数，但是a可能为负数,b是正数, 所以gcd完全可能是负数,所以b除以gcd之后完全可能是负数, 所以这里分类讨论
		if (b>0)
		{
			while(x<0)x+=b;
			while(x>b)x-=b;
		}
		else
		{
			while(x<0)x-=b;
			while(x>-b)x+=b;
		} // 最后x是ax+by=c的最小正整数解. 而一旦不定方程一个变元确定了,另一个变元也就确定了,只是题目不需要我们确定另一个变元而已
		printf("%I64d\n", x);
	}
	return 0;
}

ac情况

Status Accepted
Time 422ms
Memory 84kB
Length 1022
Lang C++
Submitted 2019-08-17 15:49:35
Shared
RemoteRunId 20757248

参考

【1】https://yfsyfs.github.io/2019/08/17/zzuli-oj-1062-%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0-%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E6%A8%A1%E6%9D%BF/