解题思路

m×n 的土地要分割成同样大的正方形且没有剩余，问最大边长。

核心：最大公约数。

要能正好分成同样大的正方形，边长必须同时是 m 和 n 的因数。要最大，就是取 m 和 n 的最大公约数（gcd）。

为什么？ 比如 6×4 的土地，能整除 6 和 4 的最大数（公约数）是 2，所以最大正方形边长是 2。

怎么求最大公约数？ 用辗转相除法：

• 如果 n 能整除 m，最大公约数就是 n
• 否则，求 n 和 m%n 的最大公约数（递归）

注意：m、n 最大到 10^18，int 装不下，要用 long long。

举例：6 和 4

• gcd(6,4) = gcd(4,2) = gcd(2,0)... 用递归：6%4=2，gcd(4,2)，4%2=0，返回 2

参考代码

#include <iostream>
using namespace std;

long long gys(long long n, long long m) {
    if (n % m == 0) {
        return m;
    } else {
        return gys(m, n % m);
    }
}

int main() {
    long long m, n;
    cin >> m >> n;

    cout << gys(m, n);  // 最大边长 = 最大公约数
    return 0;
}

复杂度分析

• 时间复杂度：O(log N)，辗转相除很快
• 空间复杂度：O(log N)，递归深度