问题 C: 上海市十二月月赛-丙组-第3题-折纸
时间限制: 1 Sec 内存限制: 128 MB提交: 48 解决: 11
[提交] [状态] [讨论版] [命题人:]
题目描述
小爱手中有一张矩形纸张，他想把这张纸分成若干正方形纸片，具体分法如下：
第1步：小爱会先确定纸张的长宽，假设短边长度为n，长边长度为m。
第2步：小爱会将短边沿直角平分线对折后剪去，从而得到一个n×n的方形纸片。
第3步：若还有剩余，小爱会将剩余的长宽为n∗(m−n)的纸张作为现有纸张，代入第一步后重复之前过程，直至没有之后纸张剩余为止。
请问按如上操作，小爱最终会得到几张方形纸片？
例如：一开始，小爱有一张 10×6 的纸张，按他的分割方法，最终他可以获得 4 张方形纸片，具体过程如下图所示：
第1步：小爱会先确定纸张的长宽，假设短边长度为n，长边长度为m。
第2步：小爱会将短边沿直角平分线对折后剪去，从而得到一个n×n的方形纸片。
第3步：若还有剩余，小爱会将剩余的长宽为n∗(m−n)的纸张作为现有纸张，代入第一步后重复之前过程，直至没有之后纸张剩余为止。
请问按如上操作，小爱最终会得到几张方形纸片？
例如：一开始，小爱有一张 10×6 的纸张，按他的分割方法，最终他可以获得 4 张方形纸片，具体过程如下图所示：
输入
输入共两个正整数，表示初始矩形纸张的长宽n,m
1<=n,m<=1013
1<=n,m<=1013
输出
输出题目所求能获得的矩形个数
样例输入 Copy
10 6
样例输出 Copy
4