题目描述
有两个闹钟。
第一个闹钟会在 b,b+a,b+2a,b+3a,…
时刻响铃。
第二个闹钟会在 d,d+c,d+2c,d+3c,…
时刻响铃。
请计算两个闹钟第一次同时响铃的具体时刻。
输入格式
第一行包含两个整数 a,b
。
第二行包含两个整数 c,d
。
输出格式
一个整数,表示第一次同时响铃的具体时刻。
如果永远都不可能同时响铃,则输出 −1
。
数据范围
所有测试点满足 1≤a,b,c,d≤100
。
样例
20 2
9 19
输出样例1:
82
输入样例2:
2 1
16 12
输出样例2:
-1
算法1
b+ma=d+nc,朴素想法是枚举m、n判断是否相等
我们可以变形等式n=(b+ma-d)/c
这样只需枚举 m,判断(b+ma-d)/c是否为自然数,即(b+ma-d)%c==0
又(b+ma-d)%c==(b+(m+c)a-d)%c==0 所以只需要枚举c次就可以
为了保证被除数大于0,需要特判一下 如果b-d<0 就加上x*a使其大于等于0 x=(d-b+a-1)/a) 就是(d-b)/a的向上取整
时间复杂度
参考文献
C++ 代码
include[HTML_REMOVED]
using namespace std;
int main()
{
int a,b,c,d,t;
cin>>a>>b>>c>>d;
t=b-d;
if(t<0)
t+=((d-b+a-1)/a)*a;
for(int i=0;i<c;i++)
{
if(t%c==0)
{
cout<<t+d;
return 0;
}
t+=a;
}
cout<<”-1”;
return 0;
}