AcWing 3683：长方形中的正方形 ← 复旦大学考研机试题
【题目来源】
https://www.acwing.com/problem/content/3686/
【题目描述】
给出长方形的长和宽，每次从长方形里撕去最大的正方形，输出最后能得到多少正方形。
【输入格式】
一行，两个整数 n，m。
【输出格式】
一个整数，表示最后能得到多少正方形。
【数据范围】
1≤n,m≤10^9
【输入样例】
3 4
【输出样例】
4
【算法分析】
● 数据范围达到 10^9，故变量声明为 long long 型。
● 本题利用求余（%）运算，不会 TLE。否则，若将代码中的选择结构改为如下代码，虽在逻辑上没有问题，但由于数据量大，所以必然会 TLE。
//select statements causing TLE
if(n>m) n=n-m;
else m=m-n;【算法代码】
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,m;
LL cnt;
int main() {
cin>>n>>m;
while(n && m) {
if(n>m) cnt=cnt+n/m,n=n%m;
else cnt=cnt+m/n,m=m%n;
}
cout<<cnt<<endl;
return 0;
}
/*
in:
3 4
out:
4
*/
【参考文献】
https://www.acwing.com/problem/content/solution/3686/1/