问题 U: Snack

问题 U: Snack

时间限制: 1.000 Sec  内存限制: 128 MB


提交


状态

题目描述

Takahashi is organizing a party.

At the party, each guest will receive one or more snack pieces.

Takahashi predicts that the number of guests at this party will be A or B.

Find the minimum number of pieces that can be evenly distributed to the guests in both of the cases predicted.

We assume that a piece cannot be divided and distributed to multiple guests.

Constraints

·1≤A,B≤105

·A≠B

·All values in input are integers.

输入

Input is given from Standard Input in the following format:

A B

输出

Print the minimum number of pieces that can be evenly distributed to the guests in both of the cases with A guests and B guests.

样例输入 Copy

【样例1】
2 3
【样例2】
123 456
【样例3】
100000 99999

样例输出 Copy

【样例1】
6
【样例2】
18696
【样例3】
9999900000

提示

样例1解释

When we have six snack pieces, each guest can take three pieces if we have two guests, and each guest can take two if we have three guests.

思路分析：要满足两个数都符合最小的平均数的意思就是找出这两个数的最小公倍数。

故只需要使用寻找两个数的最小公倍数的算法即可！！！

附上寻找最小公倍数的链接：

C语言求两个正整数的最小公倍数_-SwaggyP的博客-CSDN博客_c语言求两个正整数的最小公倍数

AC代码：

#include <iostream>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int lcm4(int m,int n)
{
    while(m!=n)
	{
		if(m>n)
		{
			m=m-n;
		}else
		{
			n=n-m;
		}	
	}
	return n;
}

int main(int argc, char** argv) {
	long long int a,b;
	cin>>a>>b;
	cout<<a*b/lcm4(a,b);
	return 0;
}

如有更好思路，请指教！！！