SWUST OJ 青蛙的约会之二(0481)
2024-09-07 03:50:24
青蛙的约会之二(0481)
Time limit(ms): 1000 Memory limit(kb): 65535 Submission: 138 Accepted: 28
Description
两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝着对方那里跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
Input
输入包括多个测试数据。每个测试数据包括一行5个整数x,y,m,n,L,其中x≠y,m、n≠0,L>0。m,n的符号表示了相应的青蛙的前进方向。
Output
对于每个测试数据,在单独一行里输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行“Impossible”。
Sample Input
1 2 3 4 5
Sample Output
4
Hint
Source
#include<iostream>
using namespace std; long long int exgcd(long long int a,long long int b,long long int &x,long long int &y)
{
if(b==)
{
x=;
y=;
return a;
}
long long int gcd=exgcd(b,a%b,x,y);
long long int x2=x,y2=y;
x=y2;
y=x2-(a/b)*y2;
return gcd;
} int main()
{
long long int x,y,n,m,l,a,b,c,gcd;
while(cin>>x>>y>>m>>n>>l)
{
a=n-m;
b=l;
c=x-y;
gcd=exgcd(a,b,x,y);
if(c%gcd!=)
cout<<"Impossible"<<endl;
else
{
c/=gcd;
x*=c;
x=(x%b+b)%b;
cout<<x<<endl;
}
}
return ;
}
注:设输出结果为 s,则(m*s+x)-(n*s+y)= kl (k∈Z),即(n-m)*s + kl = x-y,设 a=n-m,b=l,c=x-y,即as+bk=c (ax+by=c),求最小正整数x,这里要用到扩展欧几里得算法(Extended Euclidean Algorithm)。
最新文章
- JSP中文乱码问题
- 最大流 总结&;&;做题记录
- lxde桌面默认快捷键
- 卷积神经网络Convolutional Neural Networks
- ZOOKEEPER在CENTOS6上的再安装
- java.lang.NoClassDefFoundError: javax/servlet/AsyncContext
- xcode6 中增加SDWebImage/SDWebImageDownloaderOperation.m报错解决方法
- POPTEST老李谈Debug和Release的区别(c#) 1
- VR全景智慧城市—你的掌上步行街
- 使用localstorage来存储页面信息
- 2. Java面向对象之泛型-构造方法中使用
- flask(一)之路由和视图
- office图标(word,powerpoint,excel)异常(变成白板)问题修复
- Z30云台PC控制问题
- PostgreSQL 列出所有表名和数据库名, 删除session被占用的数据库
- Git图形化界面客户端大汇总
- http协议解析过程
- python 生成唯一识别码
- 【Algorithm】希尔排序
- StringUtils学习
热门文章
- 使用GitHub管理Repository
- 谷歌发布自家物理密匙TitanKey,能让人们远离互联网“黑洞”吗?
- Android 5.0 5.1 webview 闪退问题
- Opencv笔记(四)——绘图函数
- Eclipse 中 Syntax error on token ";Invalid Character";, delete this token 的解决
- 正则表达式中 /s 可以帮助“.”匹配所有的字符,包括换行,从而实现【\d\D】的功能
- python_检测一些特定的服务端口有没有被占用
- ionic3 发布订阅者模式实现
- 博客框架 Hexo: 3.9.0 及主题 NexT 6.x.x 基本操作
- day17-反射