本题考察扩展欧几里得算法，几乎无需做任何变形，但最重要的是明白扩展欧几里得算法的实现和原理
扩展欧几里得算法的目标是求解 a、b 已知的不定方程 a * x + b * y = gcd(a, b) 的解。数学上解释这个方程的解法为：只要找到一个特解 x0、y0，就能直到方程的通解为
1
2
3
| 令 c = gcd(a, b)，t 为任意数
x = x0 + b / c * t
y = y0 - a / c * t
|
同时，在使用辗转相除法求最大公约数的时候知道，gcd(b, a % b) = gcd(a, b)，所以原来的不定方程还可以写成 b * x1 + (a % b) * y1 = gcd(a, b)，而 a % b = a - a / b * b（除法结果取整），不难得到：
1
2
3
4
5
6
| gcd(a, b) = b * x1 + (a-a / b * b) * y1
= b * x1 + a * y1 – a / b * b * y1
= a * y1 + b * (x1 – a / b * y1)
所以，可以得出：
x = y1
y = x1 - a / b * y1
|
这样，我们就得到了将 a、b 递推为 b、a % b 的时候对应的不定方程的解和原解的递推关系。而一旦递推关系确立，就可以使用递归方法不断递推 a、b 的值从而求出不定方程的解。递归的边界条件也很好确定，类比欧几里得算法，即 b 递推为 0 时，a 必对应为 gcd(a, b)，这个时候只要 x 为 1 就好，y 可以为任意取值。
最后，扩展欧几里得算法使用 Java 形式描述为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Example {
int x, y;
int exgcd(int a, int b) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int re = exgcd(a, a % b);
int temp = x;
x = y;
y = x - a / b * y;
return re;
}
}
|
先从数学性质上处理一直条件，本题实际就是求解同余方程：
1
| x + am ≡ y + an (mod L) （其中 a 为任意正整数）
|
也就是：
1
| a(m − n) ≡ y − x (mod L)
|
那么，把上述式子转化为不定方程就是：
因为 m、n、L 都是已知的，可以使用扩展欧几里得算法求解方程
1
| a1(m - n) + Lk1 = gcd(m - n, L)
|
所以，要令题目有解必有 gcd(m - n, L) 为 y - x 的因数；另外，也要注意 m 和 n 相等，且 y 和 x 不等的时候也无解。最后，可以得到
1
2
| 令 c = y - x 且 d = gcd(m - n, L) 可以得到 a 的一个特解
a0 = a1 * c / d
|
但是，这样的解只是不定方程的一个解，而题目要求的是最小正整数解，所以要利用这个方程的通解式子，即：
1
2
| 令 d = gcd(m - n, L) 则
a = a0 + L / d * t （t 为任意数）
|
这样不断变化 t 的值求得最小正整数 a 就是题目的解。但是，这样不断变化 t 的办法还是太笨拙，实际观察上述式子可以知道：
L / d 为正整数，且如果 a0 小于零，则 t 必为正整数，不断加上 L / d 的整数倍，最后令 a 大于零；如果 a0 大于零，则 t 必为负整数，不断减去 L / d 的整数倍，最后令 a 尽量靠近 0。
其实，这样的做法就是模拟了求余数运算，即本题的解应该为 (a0 + L / d * t) % (L / d)。
另外，因为扩展欧几里得算法可能求出一个很大的负数解，令 a0 + L / d * t 为负数，最后求余数运算结果也可能为负数，为了保证结果正确，要在加上 L / d 后再求一次余数。
最后，必须注意，本题数据范围较大应该使用 long 类型存储。
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
| import java.util.Scanner;
public class Main {
private static long p, q;
private static long exgcd(long a, long b) {
if (b == 0) {
p = 1;
q = 0;
return a;
}
long re = exgcd(b, a % b);
long p0 = p;
p = q;
q = p0 - a / b * q;
return re;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long x = in.nextLong();
long y = in.nextLong();
long m = in.nextLong();
long n = in.nextLong();
long l = in.nextLong();
if (m == n && x != y) {
System.out.println("Impossible");
} else {
if (m < n) {
long t = m;
m = n;
n = t;
t = x;
x = y;
y = t;
}
long c = y - x;
long d = exgcd(m - n, l);
if (c % d != 0) {
System.out.println("Impossible");
} else {
System.out.println(((p * c / d) % (l / d) + l / d) % (l / d));
}
}
}
}
|
扩展欧几里德算法详解