POJ 1061 青蛙的约会——扩展欧几里得

POJ 1061 青蛙的约会——扩展欧几里得

首先我们先来介绍一下欧几里得算法和扩展欧几里得算法：

欧几里得算法又称辗转相除法，用于计算两个整数a,b的最大公约数gcd(a,b),代码如下：

int gcd(int a, int b) { return b ? gcd(b, a % b) : a;}

扩展欧几里得算法的描述：

对于不完全为0的非负整数a,b,gcd(a,b)表示a,b的最大公约数,必然存在整数对x,y，使得gcd(a,b) = ax + by.

扩展欧几里得常用在求解 模线性方程及方程组 ,代码如下：

(递归结束后x,y的值变成了最小整数解,函数最终返回值为a和b的最大公约数)

int ex_gcd(int a, int b, int &x, int &y) { if (b == 0) { x = 1, y = 0; return a; } int q = ex_gcd(b, a % b, y, x); y -= a / b * x; return q;}

然后我们来解决这个问题：

题目中设青蛙a的出发点坐标是x，青蛙b的出发点坐标是y。青蛙a一次跳m米，青蛙b一次跳n米。维度线总长L米。这些都是已知的。

我们设两只青蛙跳了t次相遇，此时两只青蛙跳的圈数相差k圈。

则有 (x + m * t) - (y + n * t) = L * k;(路程的差等于周长的整数倍)。

转化一下： (n - m) * t + L * k = x - y;

设a = n - m, b = L,c = gcd(a, b), d = x - y;(使常量看起来更直观)

则有a * t + b * k = d;

根据扩展欧几里得定理：

a * t0 + b * k0 = c一定有解(这里的t0, k0不是要求的t, k, 要加以区分)

则a * t0 * (d / c) + b * k0 * (d / c) = d也一定有解

要想a * t + b * k = d有解,那么(d / c)必须是整数，否则无解。

现在我们貌似可以看出题目的解t =  t0 * (d / c), 但这样的话t可能是负数,对于这种情况：

t = ( (to * (d/c)) % (b / c) + (b / c) ) % (b / c),这个式子是根据t的通解形式得出的，记住就好

#include using namespace std;typedef long long ll;ll x, y, m, n, L;ll t, k, a, b, c, d;ll ex_gcd(ll a, ll b, ll &t0, ll &k0) { if (b == 0) { t0 = 1, k0 = 0; return a; } ll q = ex_gcd(b, a % b, k0, t0); k0 -= a / b * t0; return q;}int main(){ bool error = false; cin >> x >> y >> m >> n >> L; if (n == m) error = true; else { a = n - m; b = L; c = ex_gcd(a, b, t, k); d = x - y; if (d % c != 0) error = true; } if (error) cout << "Impossible" << endl; else { cout << (((d/c)*t)%b + b) % b << endl; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。