题目传送门

蒟蒻的第一篇题解

题目大意

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

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

输入样例

1
2
3
4

2 3
1 2
0 0

输出样例

1
2
3

6
2

思路

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

这个题分这么几步解决：

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

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

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

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

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

上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//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 普及组] 最大公约数和最小公倍数问题