[题目描述
修罗王和邪狼被关进监狱, 该监狱的地下秩序实际被不少暗势力所把持, 这些暗势力根据其实力不同, 划分出了大大小小的势力范围具体划分方式是这样的: 监狱是一个给定的矩形, 每一个暗势力的势力范围都必须是一个正方形, 划分时, 最大的暗势力尽可能多地从矩形中划分一块正方形, 接下来, 第二大的暗势力在剩下的矩形中尽可能多的划分一块正方形例如, 图 2.1 中所示是一个 3×4 的矩阵, 可最少划分为4个势力范围
也就是说, 取走一个 3×3 的正方形后, 将问题规模变成 3×1, 然后变成 2×1, 最后变成 1×1 规模每缩小一次, 正方形的个数加 1
输入
两个 int 整数, 即长和宽
输出
正方形个数
样例输入
3 4
样例输出
4
- #include <iostream>
- #include <bits/stdc++.h>
- using namespace std;
- int main()
- {
- int n,m,cnt=1;
- scanf("%d%d",&n,&m);
- if(n<m)
- swap(n,m);
- while(n^m)
- {
- cnt++;
- n-=m;
- if(n<m)
- swap(n,m);
- }
- cout << cnt << endl;
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2497860.html