题目描述
两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。
它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。
可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。
不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。
但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。
为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。
设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。
青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。
纬度线总长L米。
现在要你求出它们跳了几次以后才会碰面。
输入格式
输入只包括一行5个整数x,y,m,n,L,其中x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000。
输出格式
输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行”Impossible”
数据范围
x≠y<2000000000,
0<m,n<2000000000,
0<L<2100000000
输入样例:
1 2 3 4 5
输出样例:
4
思路
a:青蛙a的起点
b:青蛙b的起点
m:青蛙a一次能跳多远
n:青蛙b一次能跳多远
L:一圈的距离
(b-a):a要追b多少米
(m-n):每跳一次,a能追b多少米
x是总共跳了多少次
y是a追b不一定会在一圈内追完,而是追了y圈
(m - n)*x = b - a + y*L
(m - n)*x - y*L = b - a
——————— — —————
已知 已知 已知
扩展欧几里得求的是
ax+by=d
a已知,b已知,d是a和b的最大公约数,求x,y
因此把上式的a替换乘(m-n),b替换成L。
式子变成(m-n)*x+(-y)*L=d
如果(b-a)%d不等于0,两只青蛙永远不会碰面
如果(b-a)%d等于零,把(m-n)*x+(-y)*L=d扩大(b-a)/d倍后,x就是结果。
参考文献
算法提高课Y总视频
C++ 代码
#include<iostream>
using namespace std;
typedef long long LL;
int exgcd(int a,int b,LL &x,LL &y){//扩展欧几里得算法
if(b==0){
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main()
{
int a,b,m,n,l;
cin>>a>>b>>m>>n>>l;
LL x=0,y=0;
int d=exgcd(m-n,l,x,y);
if((b-a)%d) puts("Impossible");//永远也碰不到
else
{
x=(b-a)/d*x;//按照比例扩大
LL t=abs(l/d);//具体的看评论。感谢Whisper_Rain 。
cout<< (x%t+t)%t <<endl;//返回正的余数
}
return 0;
}
写的应该还好吧~
完结撒花~
请问为什么x0等比例放大时,x=x0+k*b/d,b/d不需要等比例放大呢?
因为x的增量为b/d,y的减量为a/d,ax+by中二者相加为0,因此只需要将x0等比例放大,而不需要将b/d等比例放大
那为什么我b/d扩大之后就错了啊,按理说不应该啊
放大b的话也需要放大d
因为不定方程的通解的形式就是x=x0+k*(b/d)
如果把后面的也放大的话就会漏很多解因为本来k是属于整数的但是如果你乘上一个数的话k实际的取值就是那个数的倍数了因此会丢掉很多的解当然就有可能丢掉最小的解就有可能出错
为什么爆int
少了个
和b
吧已更正。感谢~
orz..我也想知道《大佬是如何练成》
LL t=abs(l/d);
大佬,为什么t等于这个呀,这个是什么
通解的单位变元?不知道怎么叫比较合适。
您先搞清楚一点,
exgcd
解出来的那么一组x,y
并不是我们所求的最小正整数解,它甚至可能是一个负的不知道哪里去的一个数。它们仅仅是一组解。而关于通解,假设我们解出一组解x0,y0
,方程是ax+by=c
,通解就是x=x0+k b/gcd(a,b)
,k是任意的一个整数,t
就是后面那一坨,就是b/gcd(a,b)
。所以我们要求出这个单位变量,从而得到我们所需要的最小正整数解。
谢谢同学
忙着刷题没来得及回,对不起。。
谢谢,已经搞清楚了,^_^
怎么不能给评论👍呢^ ^
为什么通解是这个式子呢?
正确性代入显然,最小的原因记不得了 上网查查吧
为什么要
abs
?👍
m-n 不一定为正整数
通解=特殊解+齐次解,但严谨证明我看不懂。。。然后不知道exgcd以及扩展怎么求ax+by=c还是上网查查具体证明过程
找到了,可以参考这篇文章
ax+bx=gcd(a,b)的通解是:x=x0+kb/gcd(a,b),y=y0-ka/gcd(a,b) ,成对写出来是不是好理解些?再在通解里面找正整数解。