题解：P14039 [PAIO 2025] Cake

· · 题解

题解：P14039 [PAIO 2025] Cake

思路：

  1. 切割规则：每次切割时，从当前矩形中切出的最大正方形的边长等于当前矩形的较短边。例如，对于一个尺寸为 a \times b（其中 a \geq b）的矩形，最大正方形的边长为 b，可以切出 a // b 个这样的正方形（其实有点类似于辗转相除法）。
  2. 按照上述过程切出正方形后，剩余的矩形尺寸为 b \times (a \% b)。
  3. 重复上述过程，直到剩余矩形的一边为0（即完全切割完了）。每次切割出的正方形数量累加即为总块数。

切割实现方法为循环切割：在每次循环中，计算当前可切割的正方形数量（即 a // b），并累加到总块数中。然后更新 a 和 b 为剩余矩形的尺寸（即 b 和 a \% b）。

代码

#include<bits/stdc++.h>
using namespace std;

int count_square_cakes(int n,int m){
    int a=max(n,m);
    int b=min(n,m);
    int cnt=0;

    while(b!=0){
        cnt+=a/b;
        int tp=a%b;
        a=b;
        b=tp;
    }

    return cnt;
}

时间复杂度：O(\log(\min(N, M)))，能处理题目中的 N, M \leq 10^9 和 T \leq 200000）的数据范围。