P4747 土地分割（入门）

解题思路

第一步：看懂题目。 把一块 m×n 米的土地分割成同样大的正方形，要求没有剩余，问最大正方形的边长是多少。

第二步：转化成最大公因数问题。 这个问题其实就是求 m 和 n 的最大公因数（GCD）。因为正方形必须同时能“正好排满”长和宽，边长必须是 m 的因数，也必须是 n 的因数，最大的公共边长就是最大公因数。

第三步：举个例子理解。 6 米 × 4 米：6 的因数有 1、2、3、6，4 的因数有 1、2、4，公共因数是 1、2，最大的是 2，所以最大正方形边长是 2 米，和样例一致。题目还配了图，图上把 6×4 的土地分成了 2×2 的小正方形，正好 6 个，完美验证了答案。

第四步：怎么求最大公因数？——辗转相除法。 用辗转相除法（也叫欧几里得算法）：gcd(a,b)，如果 b=0，答案就是 a；否则 gcd(a,b)=gcd(b, a mod b)。因为 a mod b 比 b 小，反复做下去，数字越来越小，最后一定能得到答案。例如 gcd(6,4)=gcd(4,2)=gcd(2,0)=2。

第五步：注意数据大小。 题目说 m,n≤10^18，数字非常大！int 最多存大约 21 亿，不够用，所以要用 long long 类型（可以存到 9×10^18 左右）。

第六步：注意边界情况。 如果其中一个是 0，gcd 的结果就是另一个数；但按常识土地边长至少 1，gcd 的结果至少是 1，满足“最少不能少于1米×1米”的要求。

参考代码

// 土地分割：求m和n的最大公因数（辗转相除法）
#include <iostream>

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    long long m, n;
    std::cin >> m >> n;
    std::cout << gcd(m, n) << "\n";
    return 0;
}

复杂度分析

辗转相除法每次取余后，数字至少缩小一半，所以递归次数大约是 O(log(max(m,n)))。当 m、n 达到 10^18 时，最多只要递归几十次就能出结果，速度非常快。空间上递归深度也是 O(log) 级别，可以忽略。整个程序既简单又高效，是求最大公因数的经典做法。