1103: 地盘划分（New Online Judge）

1103: 地盘划分（New Online Judge）

题目描述

对于一个n*m的矩形，最少可以划分成多少个正方形。

输入

输入存在多组测试数据，每组测试数据输入两个正整数n,m，n,m不超过10^9。

输出

对于每组测试数据输出一行表示答案

样例输入

3 4
2 2

样例输出

4
1

提示信息

每次使用较短的那条边作为正方形的边的长度，可以保证正方形个数最少

题解1（C++版本）

#include<bits/stdc++.h>
using namespace std;

int n, m;

int dfs(int x, int y){
   
	if(x <= 0 || y <= 0) return 0;
	if(x == y) return 1;
	return x/y + dfs(y, x%y);
}
int main(){
   
	while(~scanf("%d%d", &n, &m)){
   
		if(n < m) swap(n, m);
		printf("%d\n", dfs(n, m));
	}
	return 0;
}