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

题目描述

小爱有一张矩形纸张，按照以下步骤将其分割为若干正方形纸片：

设短边长度为 $n$，长边长度为 $m$（保证 $n \leq m$）

沿短边对折剪去，得到一个 $n \times n$ 的正方形纸片

剩余部分为 $n \times (m-n)$ 的矩形（若 $m-n > 0$），重复步骤1

求最终获得的正方形纸片总数。

输入格式

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

输出格式

一个整数，表示能获得的正方形纸片个数

10 6

4

数据规模与约定

对于 $30$ 的数据：$1 \leq n, m \leq 100$

对于 $60$ 的数据：$1 \leq n, m \leq 10^7$

对于 $100$ 的数据：$1 \leq n, m \leq 10^{13}$