ma+b=nc+d

92 阅读 0 评论 61 点赞

我是靠谱客的博主真实跳跳糖，这篇文章主要介绍m*a+b=n*c+d，现在分享给大家，希望可以做个参考。

The Monster

A monster is chasing after Rick and Morty on another planet. They're so frightened that sometimes they scream. More accurately, Rick screams at times b, b + a, b + 2a, b + 3a, ... and Morty screams at times d, d + c, d + 2c, d + 3c, ....

The Monster will catch them if at any point they scream at the same time, so it wants to know when it will catch them (the first time they scream at the same time) or that they will never scream at the same time.

Input

The first line of input contains two integers a and b (1 ≤ a, b ≤ 100).

The second line contains two integers c and d (1 ≤ c, d ≤ 100).

Output

Print the first time Rick and Morty will scream at the same time, or - 1 if they will never scream at the same time.

分析：

求是否有m*a+b=n*c+d。

思路1:在1~10^5做标记，m*a+b与n*c+d重合输出否则输出-1.

鉴于上述太没有技术含量有了思路2

思路2：令t=b-d。上式变为m*a+t=n*c→n=(m*a+t)/c。

c的范围已知1~100那(m*a+t)%c至多100种可能，而且一旦产生循环表示不存在整数n。所以循环条件为(m*a+t)%c！=0.

参考代码：

#include<iostream>
#include<cstring>
using namespace std;
bool time[101];

int main()
{
	bool flag = true;
	int a, b;
	int c, d;
	cin >> a >> b;
	cin >> c >> d;
	memset(time, 0, (c + 1) * sizeof(int));
	long long t =  b - d;
	while (t < 0)
	{
		t += a;
	}
	while (!time[t%c] && t%c)
	{
		time[t%c] = 1;
		t += a;
	}
	if (t%c) cout << -1 << endl;
	else
		cout << t + d<<endl;
	return 0;
}