【洛谷】【扩欧】P1516 青蛙的约会
2024-10-16 22:45:19
【题目描述】
两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
【输入格式】
输入只包括一行5个整数x,y,m,n,L
其中0<x≠y < =2000000000,0 < m、n < =2000000000,0 < L < =2100000000。
【输出格式】
输出碰面所需要的天数,如果永远不可能碰面则输出一行"Impossible"。
【算法分析:】
设最少需要的次数为k,容易得出:
求一个非负整数k,使得:
可以看出,问题变成了求不定方程的x的非负最小值
求出一组x、y,使得ax+by=gcd(a,b):
ax + by = gcd(a, b)
= gcd(b, a % b)
= bx' + (a % b)y'
= bx' + (a - [a / b] * b)y'
= bx' + ay' - [a / b] * by'
= ay' + b(x' - [a / b]y') ∴x = y', y = x' - [a / b] * y' 终止条件:
b = 0时:a * + b * = a
即x = , y =
递归求解
扩展欧几里得
求出一组ax+by=c的解:
用扩展欧几里得先求出ax' + by' = gcd(a, b)的一组解, x', y'及gcd(a, b)的值 若c mod gcd(a, b) ≠
方程无解(整数范围内) 令:
c = gcd(a, b) * k
∴k = c / gcd(a, b)
∴ax + by = c
= k * gcd(a, b)
∴ax + by = akx' + bky'
根据恒等定理:
ax = akx', by = bky'
∵a != 且 b !=
∴x = kx', y = ky'
∵k = c / gcd(a, b)
∴x = x' * c / gcd(a, b)
y = y' * c / gcd(a, b)
不定方程(同余方程)
使得x非负且最小:
用扩展欧几里得先求出ax' + by' = gcd(a, b)的一组解, x', y'及gcd(a, b)的值
lcm(a, b) = a * b / gcd(a, b) ax + lcm(a, b) + by - lcm(a, b) = c
ax + a * b / gcd(a, b) + by - a * b / gcd(a, b) = c
a(x + b / gcd(a, b)) + b(y - a / gcd(a, b)) = c
∴x + 或 - 任意倍数的b / gcd(a, b)均有对应的y的整数解 设 t = b / gcd(a, b)
x = ((x' * c / gcd(a, b)) % t + t) % t 为方程的最小非负解.
x非负且最小
扩欧代码及详解见我的github:
DEVILK1
【代码:】
#include<iostream>
#include<cstdio>
using namespace std; int x, y, m, n, l; int read() {
int x = , f = ; char ch = getchar();
while(ch < '' || ch > '') {
if(ch == '-') f = -;
ch = getchar();
}
while(ch >= '' && ch <= '')
x = (x << ) + (x << ) + (ch ^ ),
ch = getchar();
return x * f;
} int ex_gcd(int a, int b, int &x, int &y) {
if(b == ) {
x = , y = ;
return a;
}
int g = ex_gcd(b, a % b, y, x);
y -= a / b * x;
return g;
} int main() {
x = read(), y = read();
m = read(), n = read();
l = read();
int a = n - m, c = x - y;
if(a < ) a = -a, c = -c;
int x0, y0;
int g = ex_gcd(a, l, x0, y0);
if(c % g != ) {
puts("Impossible");
return ;
}
int t = l / g;
x0 = ((1LL * x0 * c / g) % t + t) % t;
cout << x0 << endl;
}
最新文章
- Spark SQL 之 Data Sources
- 第一课 ionic 日志输出
- js获取浏览器前缀
- svg学习(八)polyline
- C#判断程序是由Windows服务启动还是用户启动
- init: Associated with Deployer &#39;Catalina:type=Deployer,host=localhost&#39;
- (转载)Java NIO:NIO原理分析(二)
- Ubuntu启动停止在checking battery state...
- hadoop2.2编程: 重写comparactor
- 安卓天天练练(五)CompoundButton
- 为什么你需要使用instancetype而不是id
- BZOJ 3575 道路堵塞
- 安卓MonkeyRunner源码分析之启动
- C++变量和基本类型——2.3.1引用
- 技术简历这样写,才能得到BAT面试官的青睐
- Mac iOS Mac Watch 应用和游戏编程开发工具推荐
- java课堂笔记3
- tomcat 下安装 MantisBT
- vs2015未能计算子级
- Django + Uwsgi + Nginx 实现生产环境 项目部署