poj 1061 青蛙约会（扩展欧几里德）

题目链接：

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

题目大意：

　　中文题目，题意一目了然，就是数据范围大的出奇。

解题思路：

　　假设两只青蛙都跳了T次，可以列出来不定方程：p*l + (n-m)*T == x - y。列出等式以后，利用扩展欧几里德计算不定方程的解。在求出整数最小解的地方卡了好久，好久。

想具体了解扩展欧几里德的用法和证明的话，可以看一下神牛的博文，我自认弱绞尽脑汁也写不来这么好，附上链接：http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <cmath>
 7 #include <queue>
 8 using namespace std;
 9 #define LL long long
10 LL gcd (LL a, LL b, LL &x, LL &y)//扩展欧几里德模板
11 {
12     if (b == 0)
13     {
14         x = 1;
15         y = 0;
16         return a;
17     }
18     LL r = gcd (b, a%b, x, y), t;
19     t = x;
20     x = y;
21     y = t - a / b * y;
22     return r;
23 }
24 int main ()
25 {
26     LL x, y, m, n, l;
27     while (scanf ("%lld %lld %lld %lld %lld", &x, &y, &m, &n, &l) != EOF)
28     {
29         LL u, v, a, b, c;
30         a = n - m;
31         b = l;
32         c = gcd(a, b, u, v);//求出来的u是gcd(a, b) = au + bv中的。
33         if ((x - y) % c != 0)//x*gcd(a, b) = a*u*x + b*v*x成立，才能求出题目中的解
34         {
35             printf ("Impossible
");
36             continue;
37         }
38         LL s = b / c;
39         u = u * (x - y) / c;//这个时候才是(x-y) = (n-m)*t + p*l中t的解
40         u = (u % s + s) % s;
41         printf ("%lld
", u);
42     }
43     return 0;
44 }

本文为博主原创文章，未经博主允许不得转载。