#1930. 世纪难题

世纪难题

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小Z在“定向越野”的比赛中,过关斩将,克服重重难关,快速且高效地完成了各个关卡裁判安排的任务,转眼间,小Z来到了最后一关。说来最后一关也真是有趣,把奖品锁在了一个带有电子屏幕的宝盒中,只要破解密码打开宝盒,即可获得最终的大奖,由于宝盒只有一个,所以很考验小Z的破解的速度。破解题目规则如下:将一个给定的n×m\red{n × m}矩形划分为一个个正方形,其规则是先尽可能多地从矩形中划分一块正方形,接下来,在剩下的矩形中尽可能多的划分一块正方形……,例如,图中所示是一个3×4\red{3×4}的矩阵,可最少划分为4\red{4}个正方形。 img

也就是说,取走一个3×3\red{3×3}的正方形后,将问题规模变成3×1\red{3×1},然后变成2×1\red{2×1},最后变成1×1\red{1×1}。规模每缩小一次,正方形的个数1\red{加1}。能划分的正方形的个数即为宝盒的密码,这道“世纪难题”让小Z花费了大量时间,但由于前面花费时间很少,最终还是成功打开宝箱,获得了最终的大奖。

输入格式

1\red{1}行,两个正整数n,m\red{n , m},用空格隔开

输出格式

1\red{1}行,为宝箱的密码即可划分的正方形数\red{正方形数}

样例

输入样例1

3 4

输出样例1

4

提示

对于20%\red{20\%}的数据 1<=n<=m<=100\red{1 <= n <= m <= 100}

对于40%\red{40\%}的数据 1<=n<=m<=1000\red{1 <= n <= m <= 1000}

对于60%\red{60\%}的数据 1<=n<=m<=100000\red{1 <= n <= m <= 100000}

对于100%\red{100\%}的数据 1<=n<=m<=10000000\red{1 <= n <= m <= 10000000}

函数与递归

未参加
状态
已结束
规则
IOI
题目
7
开始于
2024-7-26 9:15
结束于
2024-7-27 11:15
持续时间
26 小时
主持人
参赛人数
11