P4716 逆序乘积式2（基础）

解题思路

逆序乘积式是指形如 AB×CD=BA×DC 的式子，其中 A、B、C、D 是四个互不相同的数字。比如 12×63=21×36。题目要统计在 [m,n] 范围内一共有多少种符合要求的组合，并且把 12×63、21×36、36×21、63×12 这四种写法看成同一种组合，只算一次。

先做数学化简。设 AB=10a+b，CD=10c+d，那么 BA=10b+a，DC=10d+c。把等式展开： (10a+b)(10c+d) = (10b+a)(10d+c) 展开后两边有公共项可以抵消，最后化简得到一个非常漂亮的结果：a×c = b×d。也就是说，"AB×CD=BA×DC"这个复杂的条件，等价于"两个数的十位数字相乘等于个位数字相乘"，判断起来就非常简单了。

算法步骤如下：

1. 用两层循环枚举两个两位数 AB 和 CD，它们都要在 [m,n] 范围内。
2. 把 AB 拆成十位 a 和个位 b，把 CD 拆成十位 c 和个位 d。
3. 检查 A、B、C、D 四个数字是否互不相等，只要有两个相等就跳过。
4. 检查 a×c 是否等于 b×d，不相等就跳过。
5. 因为一个组合有四种写法，题目要求这四种写法中的数都要在范围内，也就是 AB、BA、CD、DC 四个数都要落在 [m,n] 里。
6. 去重：把四种写法 (AB,CD)、(BA,DC)、(CD,AB)、(DC,BA) 都编码成 AB×100+CD 这样的整数，取其中字典序最小的一个作为这个组合的唯一编号，用一个 bool 数组标记。第一次见到某个编号，答案加一；以后再见到同样的编号就直接跳过。

这就像同一个人的不同照片，我们只认最标准的一张，其他照片再出现也不重复计数。

参考代码

// 逆序乘积式2：统计[m,n]范围内AB*CD=BA*DC的组合数（同一种只算1次）
#include <iostream>
using namespace std;
bool cnt[10000]; // 标记某种组合是否统计过
int rev(int x) { // 交换十位与个位
    return x % 10 * 10 + x / 10;
}
int main() {
    int m, n;
    cin >> m >> n;
    int ans = 0;
    // 枚举两个两位数 AB 和 CD
    for (int ab = m; ab <= n; ab++) {
        for (int cd = m; cd <= n; cd++) {
            int ba = rev(ab), dc = rev(cd);
            // 组合中的四个数 AB、BA、CD、DC 都必须在范围内
            if (ba < m || ba > n || dc < m || dc > n) continue;
            int a = ab / 10, b = ab % 10;
            int c = cd / 10, d = cd % 10;
            // 要求A、B、C、D四个数字互不相等
            if (a == b || c == d || a == c || a == d || b == c || b == d) continue;
            // AB*CD = BA*DC 化简后等价于 a*c = b*d
            if (a * c != b * d) continue;
            // 一个组合含 12*63、21*36、36*21、63*12 四种写法，取字典序最小作为该组合的编号
            int k1 = ab * 100 + cd;
            int k2 = ba * 100 + dc;
            int k3 = cd * 100 + ab;
            int k4 = dc * 100 + ba;
            int key = k1;
            if (k2 < key) key = k2;
            if (k3 < key) key = k3;
            if (k4 < key) key = k4;
            if (!cnt[key]) {
                cnt[key] = true;
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

两层循环枚举 AB 和 CD，范围最多只有 90 个两位数，所以最多枚举 90×90=8100 对，每对只做常数次操作。时间复杂度是 O((n-m+1)²)，实际运行非常快。

空间方面，用一个大小为 10000 的 bool 数组做去重标记，因为 AB×100+CD 的最大值小于 10000。空间复杂度 O(1)，是常数级别的。