洛谷 SP5450 题解

题目传送门

蒟蒻的第一篇题解

题目大意

这道题翻译言简意赅，不用我说了吧

先吐槽一下输入输出样例，这里给出调好格式的：

输入样例

2 3
1 2
0 0

输出样例

6
2

思路

先画个毫无必要的图理解一下

这个题分这么几步解决：

• 求正方形边长
• 求横边和纵边上分别有几块地砖
• 求总共需要几块地砖

显而易见，正方形边长为 $lcm(W,H)$ （ $W$ 和 $H$ 最小公倍数）

然后不难得到，$ans=\frac{lcm(W,H)}{W}\times \frac{lcm(W,H)}{H}$，也就是横边上地砖数量 $\times$ 纵边上地砖数量。

下一步就是求 $lcm(W,H)$，通过极其复杂非常简单的思考，可以得到 $lcm(W,H)=\frac{W\times H}{gcd(W,H)}$

$gcd(W,H)$ 直接辗转相除法求就可以了

上代码

//By makerlife
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
ll gcd(ll x,ll y)//辗转相除求最大公因
{
	if(y==0) return x;
	else return gcd(y,x%y);
}
ll lcm(ll x,ll y)//求最小公倍数
{
	return x*y/gcd(x,y);
}
ll w,h;//记得开long long
int main()
{
	while(cin>>w>>h)
	{
		if(w==0 && h==0) break;
		printf("%lld\n",(lcm(w,h)/w)*(lcm(w,h)/h));
	}
	return 0;//完美结束
}

记得绑定个人账户提交SP的题啊

这里再推荐一道题

P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题