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; }
相关文章
- 036_lua应用扩展
- JNDI扩展知识
- 【干货】Chrome插件(扩展)开发全攻略 写在前面
- 小波去噪算法的简易实现及其扩展(小波锐化、高斯拉普拉斯金字塔去噪及锐化)之一。
- 谷歌浏览器扩展快捷键冲突 设置
- [php][linux]编译安装PHP7及扩展
- Chrome 扩展程序 CrxMouse 优化版 v3.0.1
- 使用Docker、Registrator、Consul、Consul Template和Nginx实现高可扩展的Web框架
- Shopify构建分布式可扩展应用的最佳实践
- 877. 扩展欧几里得算法
- Kotlin also let 内联扩展函数
- 2019牛客多校第九场AThe power of Fibonacci——扩展BM
- 大数据Flink(四十七):扩展阅读 File Sink
- 大数据Flink(四十六):扩展阅读 异步IO
- 【jzoj 1499】街道(扩展域并查集)
- jdk自带的ThreadLocal和netty扩展的FastThreadLocal比较总结
- VisualStudio 扩展开发
- 小程序开发实用技巧——扩展 Page 页面对象
- 【AMQP】macOS下的AMQP服务器以及PHP扩展搭建