题解：B4269 [朝阳区小学组 2019] square

· · 题解

之前被 Hack 了，再写一遍。

题目简述

给定一个长方形的长和宽，求这个长方形分割成若干个小正方形后正方形的边长之和的最小值。注意：正方形大小可不一致。

主要思路

为了使边长和最小，肯定要将每次分割出的正方形最大，否则内部的正方形边长也会计算。在一个长方形中分割出最大的正方形，正方形的边长即为 \min(A,B)。很容易就能想到不断使 A 或 B 不断减 B 或 A 直到为 0 的方法，但如果 |A-B| 很大，就会导致 TLE（#10）。

假设 A>B，那么 A-B 可能会很大，A 就可能是 B 的很多倍，让 A 不断减 B 就会导致减了很多次 \min(A,B) 却还是 B，所以可以直接让答案增加 \lfloor\frac{A}{B}\rfloor \cdot B，表示长为 A 宽为 B 的长方形中最大可以分割出边长为 B 的正方形且能分出 \lfloor\frac{A}{B}\rfloor 个，并使 A \gets A \bmod B，一步保证下一次计算时 A<B；反之答案增加 \lfloor\frac{B}{A}\rfloor \cdot A，并使 B \gets B \bmod A。这个过程直到 A=0 或 B=0 时停止。

注意事项

题目中只保证了数据在 long long 范围内，但如果输入是两个 long long 极限，那么一加就会炸，所以要开 unsigned long long。

AC Code

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long double db;
typedef unsigned long long ll;
const int INT_INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
// ----------------------------

// ----------------------------

// ----------------------------

int main() {
    ll a, b, ans;
    for (int i = 1; i <= 10; i++) {
        cin >> a >> b;
        ans = 0;
        while (a > 0 && b > 0) {
            if (a > b) {
                ans += a / b * b;
                a %= b;
            }
            else {
                ans += b / a * a;
                b %= a;
            }
        }
        cout << ans << endl;
    }
    return 0;
}