P10277: 折纸

---

【题目描述】

【题目描述】 小智手中有一张矩形纸张，他想把这张纸分成若干正方形纸片，具体分法如下： 第1步：小智会先确定纸张的长宽，假设短边长度为n，长边长度为 m。 第2步：小智会将短边沿直角平分线对折后剪去，从而得到一个n×n的方形纸片。 第3步：若还有剩余，小智会将剩余的长宽为n∗(m−n)的纸张作为现有纸张，代入第一步后重复之前过程，直至纸张没有剩余为止。 请问按如上操作，小智最终会得到几张方形纸片？ 例如：一开始，小智有一张 10×6 的纸张，按他的分割方法，最终他可以获得 4 张方形纸片，具体过程如下图所示： 【输入格式】 输入共两个正整数，表示初始矩形纸张的长宽n,m 【输出格式】 输出题目所求能获得的矩形个数 【数据范围】 对于30%的数据，1≤n,m≤100 对于60%的数据，1≤n,m≤10,000,000 对于100%的数据，1≤n,m≤10,000,000,000,000 【样例数据】 输入: 10 6 输出: 4

【输入】

输入共两个正整数，表示初始矩形纸张的长宽n,m

【输出】

输出题目所求能获得的矩形个数

题目类型~

思维竞速赛 

咻咻~

提交答案 状态 返回