A62492 | $square【问题描述】任意一个边长是整数的长方形都可以分割成若干个边长是正整数的正方形，分割的方式有很多种，你需要找到分割出的所有正方形边长之和最小的那一种分割方法。即：将边长为正整数A、B的长方形划分成若干边长均为正整数，且每个正方形的边均平等于长方形的相应边，试求这些正方形边之和的最小值MIN。如果这个长方形可以分成N个正方形，其中每个边长为Ci，那么MIN=C1+C2+...+CN。注意\dots$

来源2024年

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

square 【问题描述】 任意一个边长是整数的长方形都可以分割成若干个边长是正整数的正方形，分割的方式有很多种，你需要找到分割出的所有正方形边长之和最小的那一种分割方法。 即：将边长为正整数 A 、 B 的长方形划分成若干边长均为正整数，且每个正方形的边均平等于长方形的相应边，试求这些正方形边之和的最小值M IN 。 如果这个长方形可以分成N个正方形，其中每个边长为C i ，那么M IN=C 1 +C 2 +...+C N 。注意，数组C中的元素可能相等。 【输入 说明 】 一共10行，每行两个正整数，表示每个长方形的长和宽 A i 、 B i 。 【输出 说明 】 一共10行，每行一个整数，输出每个长方形分割出的正方形边长之和的最小值M IN 。 【样例输入】 112131415161718191101 【样例输出】 12345678910 【 数据范围 】 对于30% 的数据： A i,B i \leq MAXINT 对于100% 的数据： A i,B i \leq MAXLONGINT

C++ 编辑器

输入

输出