解题思路

总人数 = m×n。要变换队形，就是把人重新排成长方形或正方形，也就是把总人数拆成两个大于 1 的因数相乘。

核心思路：找总人数的因数对。

如果总人数 s 能分解成 a×b（a、b 都大于 1），就是一种变换队形。

步骤：

1. 总人数 s = m×n
2. 枚举 i 从 2 到 sqrt(s)，如果 i 是 s 的因数，就找到一对因子（i 和 s÷i），算一种变换
3. 为什么要枚举到 sqrt(s)？因为 i 超过 sqrt(s) 后，s÷i 会小于 sqrt(s)，这对因子之前已经算过了，会重复
4. 最后减 1，去掉原来的队形 m×n

举例 m=3，n=10，总人数 30：

• 30 的因子对（大于1）：2×15、3×10、5×6
• 去掉原来的 3×10，剩下 2 种变换（2×15 和 5×6）

参考代码

#include <iostream>
#include <cmath>
using namespace std;

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

    long long s = m * n;  // 总人数

    // 枚举 s 的因子对
    for (long long i = 2; i <= sqrt(s); i++) {
        if (s % i == 0) {
            num++;  // i 和 s/i 是一对因子
        }
    }

    cout << num - 1;  // 去掉原来的队形
    return 0;
}

复杂度分析

• 时间复杂度：O(√S)，枚举到 sqrt(s)
• 空间复杂度：O(1)