A25280. square问题描述任意一个边长是整数的长方形都可以分割成若干个边长是正整数的正方形，分割的方式有很多种，你需要找到分割出的所有正方形边长之和最小的那一种分割方法。即：将边长为正整数A、B的长方形划分成若干边长均为正整数，且每个正方形的边均平等于长方形的相应边，试求这些正方形边之和的最小值MIN。如果这个长方形可以分成N个正方形，其中每个边长为Ci，那么MIN=C1+C2+...+CN。注意，数…
填空题
中等
知识点
题目描述
square
问题描述
任意一个边长是整数的长方形都可以分割成若干个边长是正整数的正方形，分割的方式有很多种，你需要找到分割出的所有正方形边长之和最小的那一种分割方法。
即：将边长为正整数A、B的长方形划分成若干边长均为正整数，且每个正方形的边均平等于长方形的相应边，试求这些正方形边之和的最小值MIN。
如果这个长方形可以分成N个正方形，其中每个边长为Ci，那么MIN=C1+C2+...+CN。注意，数组C中的元素可能相等。
输入说明
一共10行，每行两个正整数，表示每个长方形的长和宽Ai、Bi。
输出说明
一共10行，每行一个整数，输出每个长方形分割出的正方形边长之和的最小值MIN。
样例输入
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1样例输出
1
2
3
4
5
6
7
8
9
10数据范围
对于30% 的数据：Ai,Bi≤MAXINT
对于100% 的数据：Ai,Bi≤MAXLONGINT
参考答案
#include <iostream>
using namespace std;
typedef unsigned long long ull;
ull solve(ull a, ull b)
{
if(a<b) return solve(b, a); // a<b时，交换
if(b==0) return 0; // b为0时，切割完毕
return a/b*b + solve(b, a%b); // a>=b时，计算
}
int main()
{
for(int i = 0; i < 10; i++)
{
ull a, b;
cin >> a >> b;
cout << solve(a, b) << '\n';
}
return 0;
}
上一题
下一题