欢迎访问 如意编程网!

如意编程网

当前位置: 首页 > 编程资源 > 编程问答 >内容正文

编程问答

江西财经大学第二届程序设计竞赛同步赛 H大时钟 (扩展欧几里得)

发布时间:2024/7/5 编程问答 0 豆豆
如意编程网 收集整理的这篇文章主要介绍了 江西财经大学第二届程序设计竞赛同步赛 H大时钟 (扩展欧几里得) 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

链接:https://ac.nowcoder.com/acm/contest/635/H
来源:牛客网

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

艾兰岛和沃夫岛的时间算法很不一样,它们都拥有它们自己的魔法大时钟。以我们的时间来看艾兰岛的大时钟起鸣在b, b+a, b+2a, b+3a,… ,(a,b均为正整数)并且沃夫岛的大时钟起鸣在d, d+c, d+2c, d+3c,….(c,d均为正整数)因为计时的方法不同,两边经常打仗,但可能有某些时间点两边的大时钟同时起鸣。我们称这样的时间点为和平点。求第一个和平点。(如果没有这样的时间点,输出-1)

输入描述:

第一行输入两个整数a,b ( 1< a,b < 5*108)

第二行输入两个整数c,d ( 1< c,d < 5*108)

输出描述:

第一个和平点所表示的时间(如果没有这样的时间点,输出-1) 示例1

输入

复制 20 2 9 19

输出

复制 82 示例2

输入

复制 2 1 16 12

输出

复制 -1

解题思路:由题目我们可以很容易列出方程b+ax=d+cy,令b<d,如果b>d我们就交换(a,c),(b,d),这样的话我们就只需要求出y的最小正整数解,然后d+cy必定是答案,我们把式子转化为ax-cy=d-b,然后再转化为ax+cy=d-b,改成求y的最大非正整数解,答案也随即变成d-cy了。
代码: #include<iostream> using namespace std; typedef long long ll; ll a,b,c,d; void exgcd(ll a,ll b,ll &x,ll &y,ll &c){if(!b){x=1,y=0,c=a;}else{exgcd(b,a%b,y,x,c);y-=a/b*x;} } int main(){cin>>a>>b>>c>>d;if(b>d){swap(b,d);swap(a,c);}ll x,y,gcd;exgcd(a,c,x,y,gcd);if((d-b)%gcd){puts("-1");return 0;}x*=(d-b)/gcd; y*=(d-b)/gcd;y%=(a/gcd);while(y>0) y-=a/gcd;cout<<d-c*y<<endl;return 0; }

 

转载于:https://www.cnblogs.com/zjl192628928/p/10776689.html

总结

以上是如意编程网为你收集整理的江西财经大学第二届程序设计竞赛同步赛 H大时钟 (扩展欧几里得)的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得如意编程网网站内容还不错,欢迎将如意编程网推荐给好友。