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

题目链接：

题目大意：

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

解题思路：

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

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

代码：

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #include <iostream>

 #include <cmath>

 #include <queue>

 using namespace std;

 #define LL long long

 LL gcd (LL a, LL b, LL &x, LL &y)//扩展欧几里德模板

 {

     if (b == )

     {

         x = ;

         y = ;

         return a;

     }

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

     t = x;

     x = y;

     y = t - a / b * y;

     return r;

 }

 int main ()

 {

     LL x, y, m, n, l;

     while (scanf ("%lld %lld %lld %lld %lld", &x, &y, &m, &n, &l) != EOF)

     {

         LL u, v, a, b, c;

         a = n - m;

         b = l;

         c = gcd(a, b, u, v);//求出来的u是gcd(a, b) = au + bv中的。

         if ((x - y) % c != )//x*gcd(a, b) = a*u*x + b*v*x成立，才能求出题目中的解

         {

             printf ("Impossible\n");

             continue;

         }

         LL s = b / c;

         u = u * (x - y) / c;//这个时候才是(x-y) = (n-m)*t + p*l中t的解

         u = (u % s + s) % s;

         printf ("%lld\n", u);

     }

     return ;

 }

巴特西

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

最新文章

热门文章