洛谷P14039题解

分析

题意

我们需要将一个 $N \times M$ 的矩形蛋糕切割成若干正方形，每次都切出当前能得到的最大正方形（该正方形至少有三条边贴着剩余矩形的边），直到蛋糕完全被切割。要求计算最终得到的正方形总数。

思路

若 $N \geq M$，可切割出 $\left\lfloor \frac{N}{M} \right\rfloor$ 个 $M \times M$ 的正方形，剩余矩形为 $(N \bmod M) \times M$。

若 $N < M$，可切割出 $\left\lfloor \frac{M}{N} \right\rfloor$ 个 $N \times N$ 的正方形，剩余矩形为 $N \times (M \bmod N)$。

重复上述过程，累计正方形总数，直至某边长度为 $0$。

代码

#include <bits/stdc++.h>
using namespace std;
int32_t count_square_cakes(int32_t N, int32_t M) {
    int32_t r = 0;
    while (N > 0 && M > 0) {
        if (N >= M) {
            r += N / M;
            N %= M;
        } else {
            r += M / N;
            M %= N;
        }
    }
    return r;
}