首页 > 代码库 > POJ1061 青蛙的约会 (扩展欧几里德)
POJ1061 青蛙的约会 (扩展欧几里德)
本文出自:http://blog.csdn.net/svitter
题意:青蛙绕圈跳, 初始位置X,Y,速度M,N,方向相反,L为模。最后能否相遇?相遇时间是什么?
本题目为扩展欧几里德,扩展欧几里德介绍:
关于扩展欧几里德方程
ax + by = c(1)
可以用来求是否有解。即是否存在c满足这个方程。
exgcd(a, b, x, y)是用来求ax + by = gcd(a, b)中x的值和y的值的。如果仅仅只是判断(1)是否有解,直接看gcd(a, b)能否整除c即可。
然后开始分析本题:
设最后在坐标s相遇,A转了b圈,B转了b`圈,花费时间为a,那么可以得到两个方程:
Ma + X = Lb + s;(3)
Na + Y = Lb` + s;(4)
如果s有解,那么方程 (M - N)a+L(b - b`) = Y - X有解。(即(3) - (4))
以此判断impossible的情况;(一开始做的时候没弄懂题意,以为不同方向,shit- -)
解出的a可能不是一个正数,或者比最小数大。
通解为
x1 = x + L / gcd(m-n, L) * t;t为任意整数;
y1 = y - L / gcd(m-n,L) * t;
证明:
已知ax + by = c
ax1 = x * a + lcm(a, b) * t;
by1 = y * b - lcm(a, b)*t;
所以ax1 + by1 = c;
代码如下:
#include <iostream> #include <stdio.h> #include <string.h> using namespace std; #define lln long long int lln gcd(lln a, lln b) { if(b == 0) return a; return gcd(b, a % b); } lln exgcd(lln a, lln b, lln &x, lln &y) { if(b == 0) { x = 1; y = 0; return a; } int d = exgcd(b, a % b, x, y); int t = x; x = y; y = t - (a / b) * y; return d; } void ace() { lln X, Y, M, N, L; lln dis; lln a, b, x, y, c, gc, d; while(scanf("%lld %lld %lld %lld %lld", &X, &Y, &M, &N, &L) == 5) { a = M - N; c = exgcd(a, L, x, y); dis = Y - X; if(dis % c != 0) { printf("Impossible\n"); continue; } x = x * (dis / c); y = y * (dis / c); gc = L / c; gc = gc > 0? gc : -gc; while(x > 0) { x -= gc; } while(x < 0) { x += gc; } printf("%lld\n", x); } } int main() { ace(); return 0; }
POJ1061 青蛙的约会 (扩展欧几里德)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。