本文主要是介绍POJ - 1061 青蛙的约会 (扩展欧几里得算法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Description
我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
Input
Output
Sample Input
1 2 3 4 5
Sample Output
4
思路:扩展欧几里得算法,设时间为t,最后在s点相遇,A走了a圈,B走了b圈,
那么我们可以推出: m*t + x = L * a + s; n*t + y = L * b + s,两式相减得:(m-n) * t + (b - a) * L = y - x,正好是扩展欧几里得的形式求两个可行解,那么对于求最小的解动脑子想想就得到了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
typedef long long ll;
using namespace std;ll gcd(ll a, ll b) {return b?gcd(b, a%b):a;
}void exgcd(ll a, ll b, ll &x, ll &y) {if (b == 0) {x = 1;y = 0;return;}exgcd(b, a%b, x, y);ll t = x;x = y;y = t - a / b * y;return;
}int main() {ll x, y, n, m, l;while (scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &l) != EOF) {ll a = n-m, b = l, c = x-y, p, q;ll g = gcd(a, b);if (c % g) {printf("Impossible\n");continue;}a /= g, b /= g, c /= g;exgcd(a, b, p, q);p *= c;ll t = p % b;while (t < 0) t += b;printf("%lld\n", t);}return 0;
}
这篇关于POJ - 1061 青蛙的约会 (扩展欧几里得算法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!