[POJ]1061 青蛙的约会

原题

http://poj.org/problem?id=1061

解法

此题用扩展欧几里得计算
(n-m) X ≡ (x-y) (mod l) 的最小正整数解
即(n-m)
X + l * Y = (x-y)

贝祖定理: ax + by = m 有整数解时当且仅当m是gcd(a,b)的倍数。
用扩展欧几里得能算出ax + by = gcd(a,b)的一个特解
此特解乘上m / gcd(a,b)得到的就是ax + by = m的特解

所有的解x mod (b/gcd(a,b))同余
所有的解y mod (a/gcd(a,b))同余

参考

https://blog.csdn.net/ccnuacmhdu/article/details/79415284
https://www.cnblogs.com/xeoncdy/p/7265419.html
https://blog.csdn.net/sun897949163/article/details/51894372
https://blog.csdn.net/yoer77/article/details/69568676

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
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>

#define LL long long
using namespace std;

LL x, y, m, n, l;


// 扩展欧几里得求二元一次方程的一个解
LL exGCD(LL a, LL b, LL&x, LL&y) {
if (b == 0) {
x = 1;// a * 1 + b * 0 = a
y = 0;
return a;
}

LL r = exGCD(b, a % b, x, y);

LL t_y = y;
y = x + (-a / b) * y;
x = t_y;

return r;//返回值为gcd
// 记法:该函数返回时满足 a * x + b * y = gcd; 调整x和y只是为了返回上一层调用后能重新调整x'和y'
// x' = y
// y' = x + (-a/b) * y
}


int main(int argc, char const *argv[]) {

scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &l);


LL a = ((n - m) % l + l ) % l;//(将X的系数化为正的)

LL x0, y0;

LL gcd = exGCD(a, l, x0, y0);

if ((!a) || (x - y) % gcd) {
printf("Impossible\n");
return 0;
}

x0 = x0 * (x - y) / gcd;// x0原先是 (n-m) * X + l * Y = gcd 的一个特解,现在将它化为 (n-m) * X + l * Y = (x-y)的特解X0

// 找出最小的正整数解X0,所有X mod (b/gcd(a,b))同余
x0 = ((x0 % (l / gcd)) + (l / gcd)) % (l / gcd);// 用%表示mod的办法
printf("%lld\n", x0);


return 0;
}