求得到指定乘积的所有可能组合数的高效算法

你的暴力枚举方法在a或b较大时效率极低，核心原因是笛卡尔积的组合数呈指数级增长。这里提供一种基于数论的高效解法，利用平方自由数的性质将问题转化为异或组合计数，彻底避免暴力枚举。

核心原理 #

任何正整数都可以拆分为 x = s * k²，其中s是平方自由数（所有质因数的指数均为1）。a个数的乘积为完全平方数的充要条件是：这a个数的平方自由部分相乘后仍是完全平方数——而平方自由数相乘为完全平方数，等价于它们的质因数集合的对称差为空（即每个质因数出现偶数次），对应平方自由数的“异或和”为1（1的质因数集合为空）。

具体实现步骤 #

1. 预处理平方自由特征 #

对1到b的每个数，计算其平方自由部分s。例如：

• 12 = 2²×3 → 平方自由部分为3
• 18 = 2×3² → 平方自由部分为2
• 4 = 2² → 平方自由部分为1

2. 统计特征频率 #

统计每个平方自由数s在1~b中的出现次数freq[s]，比如b=6时，freq为 {1:2, 2:1, 3:1, 5:1, 6:1}（1和4的平方自由部分都是1）。

3. 计算符合条件的组合数 #

根据a的大小选择合适的计算方式：

动态规划（适合a较小的场景）

定义dp[k][v]为选k个数，平方自由特征的异或和为v的组合数。初始状态dp[0][1] = 1（0个数的乘积为1，对应平方自由特征1）。递推时，对每个已有的组合状态，遍历所有可能的平方自由特征，更新新的状态：

dp_curr[new_v] += dp_prev[old_v] * freq[sf]

其中new_v是old_v与sf相乘后的平方自由部分（等价于两者的质因数对称差）。最终结果为dp[a][1]。

Walsh-Hadamard变换（适合a较大的场景）

当a很大时（比如1e4以上），动态规划的线性递推会变慢，此时可以用异或卷积的快速计算方法：将频率数组通过WHT转换到频域，进行a次幂运算后再逆变换，结果中对应1的位置的值就是所求组合数。时间复杂度为O(m log m log a)，其中m是不同平方自由特征的数量。

代码示例（动态规划版） #

import math
from collections import defaultdict

def get_square_free(x):
    """计算x的平方自由部分"""
    res = 1
    for i in range(2, int(math.isqrt(x)) + 1):
        if i*i > x:
            break
        cnt = 0
        while x % i == 0:
            cnt += 1
            x = x // i
        if cnt % 2 == 1:
            res *= i
    if x > 1:
        res *= x
    return res

def count_square_product_combinations(a, b):
    """统计a个≤b的数相乘为完全平方数的有序组合数"""
    # 统计1~b的平方自由特征频率
    freq = defaultdict(int)
    for num in range(1, b + 1):
        sf = get_square_free(num)
        freq[sf] += 1
    
    # 动态规划初始化：0个数时，乘积为1，对应平方自由特征1
    dp_prev = defaultdict(int)
    dp_prev[1] = 1
    
    for _ in range(a):
        dp_curr = defaultdict(int)
        for old_v, cnt in dp_prev.items():
            for sf, sf_cnt in freq.items():
                # 计算old_v与sf相乘后的平方自由部分，即异或结果
                new_v = get_square_free(old_v * sf)
                dp_curr[new_v] += cnt * sf_cnt
        dp_prev = dp_curr
    
    return dp_prev.get(1, 0)

# 测试原代码场景：a=2, b=3
print(count_square_product_combinations(2, 3))  # 输出3，与原代码结果一致

# 测试用户示例场景：a=3, b=6
print(count_square_product_combinations(3, 6))  # 输出所有乘积为平方数的有序组合数

效率对比 #

• 原方法时间复杂度为O(√n * b^a)，当a≥5或b≥20时会因组合数爆炸变得极慢。
• 新方法时间复杂度仅与b的大小和a的对数相关，即使b=1e5、a=1e4也能高效计算。

内容的提问来源于stack exchange，提问作者Aslan Gayzov