本文主要是介绍POJ 1061 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题是Extended Euclidean Algorithm的应用。可以看
链接1(extended euclidean algorithm)：http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
链接2(Bezout's Identity)：http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity
这里的代码是按照wikipedia上链接1的描述写的。
首先假设当两只青蛙相遇时，都跳了K步（根据题意，它们跳得步数是一样的），并且第一只青蛙比第二只青蛙多跳了c圈（c可以为负数），这样，我们有：
x + Km - (y + Kn) = cL ，即：(x - y) + K(m - n) = cL，亦即：
K(n - m) + cL = (x - y) （以下称作原方程）
这样就转化为了一个可以应用Extended Euclidean Algorithm的问题。
Extended Euclidean Algorithm可以求出ax + by = gcd(a, b)的一个整数解(x0, y0)。然后根据链接2，我们知道这个方程的所有整数解为(x, y) = (x0 + kb/g, y - ka/g)。（这点比较好验证，带进去后面部分就都消掉了）。其中k是任意整数，g=gcd(a,b).
我们让a = n - m, b = L，那么我们可以根据上述extend euclidean algorithm得到一组解(x0, y0)。这个算法还可以附带得到g = gcd(a, b)。（所以不用单独跑gcd算法）。
很容易看出，既然左边能被g整除，那么右边的(x-y)也必须能够被g整除，否则原方程无解。
我们将原方程右边记做R，即R = x - y。
否则，我们可以得到这个方程的所有解: (x, y) = (R / g * x0 + kb/g, R/g * y0 + kb/g)。
按照问题，我们只关心第一项，即K = R / g * x0 + kb/g。我们要求的是这样一组K中最小的非负整数。
做法是先让K=0，求出k（这样的整数k不一定存在，但这样我们就可以求出使得K最接近0的k），然后求K。
k = (- R/g *x0) / (b/g)
然后K = R / g * x0 + (- R/g *x0) / (b/g) * b/ g。
注：上述公式中都是整数运算。
我们用P = R/g, Q = b / g，x0 = mQ + r带入上述简化表达式，有：
K = P * (mQ + r) - P (mQ + r) / Q * Q = P*(mQ + r) - P m Q = P*r = P * (x0 % Q) = (P*x0) % Q。
即K是P*x0对Q的余数。
剩下的值得注意的就是让Q为正数就好了（可以直接取Q的绝对值，因为这时相当于k的绝对值变了）。
程序如下：
| 1061 | Accepted | 216K | 0MS | C++ | 1906B |
/*
ID: thestor1
LANG: C++
TASK: poj1061
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>using namespace std;void extend_gcd(long long a, long long b, long long &g, long long &x0, long long &y0)
{long long r0 = a, r1 = b, s0 = 1, s1 = 0, t0 = 0, t1 = 1;long long q2, r2, s2, t2;while (r1 != 0){q2 = r0 / r1;r2 = r0 - r1 * q2; // r0 % r1s2 = s0 - s1 * q2;t2 = t0 - t1 * q2;r0 = r1, r1 = r2;s0 = s1, s1 = s2;t0 = t1, t1 = t2;}// cout << a << " * " << s0 << " + " << b << " * " << t0 << " == " << r0 << "(GCD(" << a << ", " << b << "))" << endl;g = r0;x0 = s0;y0 = t0;
}int main()
{long long x, y, m, n, L;while (cin >> x >> y >> m >> n >> L){// extend_gcd(240, 46);// x + km - (y + kn) = cL // =>// (x - y) + k(m - n) = cL// =>// k(n - m) + cL = (x - y)long long a = n - m, b = L, R = x - y;long long g, x0, y0;extend_gcd(a, b, g, x0, y0);// cout << "a: " << a << ", b: " << b << ", R: " << R << endl;// cout << "g: " << g << ", x0: " << x0 << ", y0: " << y0 << endl;if (R % g != 0){cout << "Impossible" << endl;}else{long long k = R / g * x0;long long add = b / g;if (add < 0){add = -add;}cout << (k % add + add) % add << endl;}}return 0;
}这篇关于POJ 1061 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
