题解 P2660 zzc 种田【未提交】

Misophiliac · 2023-09-09 14:08:07 · 题解

前言

今天随机跳题跳到了这道 N 年前做过的题，想试试抢最优解就看了一会，不经意发现一个神奇的公式，其他题解都没有提到，就顺便记录一下。

题意简述

给一个长、宽分别为 x,y 的矩形，要求不断进行以下操作：

• 取出矩形中最大的正方形，并将其周长加到答案中。

• 从矩形去除这个正方形。

直到矩形某边为 0。

题意分析

公式：答案为 4(x+y-\gcd(x,y))。

以下是证明。

不难发现，对于长、宽分别为 a,b(a\ge b) 的矩形，我们可以一直去除最大的正方形（边长为 b）直到长小于宽，此时剩余矩形的两边分别为 b,a\bmod b，而去除的正方形个数为 \lfloor\frac{a}{b}\rfloor。

为方便，我们令 f(a,b) 表示长、宽分别为 a,b(a\ge b) 的矩形对应的正方形边长和，则有如下递归式：

（是不是有点像 \gcd？）

我们来试着化简一下：

移项，得

令 g(a,b)=a+b-f(a,b)，则 g(a,b)=g(b,a\bmod b)。

而且，f(a,0)=0，所以 g(a,0)=a。

（是不是和 \gcd 一模一样？）

于是 g(a,b)\equiv\gcd(a,b)，而 f(a,b)=a+b-\gcd(a,b)。

而结果就是 4f(x,y)。

代码

（其实没有太大的给的必要）

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long x, y;
    cin >> x >> y;
    cout << 4 * (x + y - __gcd(x, y)) << endl;
    return 0;
}