P2660. zzc 种田

发表于 分类于 阅读次数： Waline： 本文字数： 238 阅读时长 ≈ 1 分钟

考点

  • 最大公约数
  • 贪心
  • 分治

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll dfs(ll a, ll b) {
  if (!a || !b) return 0;
  return 4 * b * (a / b) + dfs(b, a % b);
}

int main() {
  ll x, y;
  cin >> x >> y;
  cout << dfs(max(x, y), min(x, y));
  return 0;
}

思路

乍一看数据范围，1e16...绝对不可能是暴力模拟

考虑贪心策略，可以发现同样大小的格子数，组成正方形得到的总周长是远小于组成矩阵的：

所以就可以得到分治策略：

每一次将大矩形分解成一个最大的正方形+小矩形

正方形的周长可以直接纳入答案内，对小矩形进行递归分解；直到长宽中的某一方可以整除另一方，代表当前是正方形

不管怎样，要么能以某个大正方形结束，要么能以边长为1的最小的正方形结束