#1930. 世纪难题
世纪难题
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
小Z在“定向越野”的比赛中,过关斩将,克服重重难关,快速且高效地完成了各个关卡裁判安排的任务,转眼间,小Z来到了最后一关。说来最后一关也真是有趣,把奖品锁在了一个带有电子屏幕的宝盒中,只要破解密码打开宝盒,即可获得最终的大奖,由于宝盒只有一个,所以很考验小Z的破解的速度。破解题目规则如下:将一个给定的矩形划分为一个个正方形,其规则是先尽可能多地从矩形中划分一块正方形,接下来,在剩下的矩形中尽可能多的划分一块正方形……,例如,图中所示是一个的矩阵,可最少划分为个正方形。
也就是说,取走一个的正方形后,将问题规模变成,然后变成,最后变成。规模每缩小一次,正方形的个数。能划分的正方形的个数即为宝盒的密码,这道“世纪难题”让小Z花费了大量时间,但由于前面花费时间很少,最终还是成功打开宝箱,获得了最终的大奖。
输入格式
共行,两个正整数,用空格隔开
输出格式
共行,为宝箱的密码即可划分的
样例
输入样例1
3 4
输出样例1
4
提示
对于的数据
对于的数据
对于的数据
对于的数据