寻找满足双模方程的数组三元组[a,b,c]的优化解法

问题描述 #

已知长度为101的数组arr，元素取值范围为1~256；给定已知量x、y、z，模数m=256。需从arr中选取索引互不重复的三个元素a、b、c，使其满足以下两个模方程：

Eq1: 3z = (a - b + 3y - x) % m + 1
Eq2: 2z = (a - c + y) % m + 1

暴力遍历所有三元排列需计算101×100×99次，现有尝试通过遍历二元排列推导c的方式减少计算量，但仍需更高效的数学优化方法。

现有尝试分析 #

现有代码通过遍历所有二元索引排列，再推导c的可能值并检查索引唯一性，复杂度为O(n²)（约101×100=10100次迭代），但存在逻辑误区：已知z是给定常量，无需从a、b反推z，完全可以通过数学变形直接建立a、b、c的确定性关系，进一步降低复杂度。

数学优化解法 #

方程变形推导 #

首先对两个模方程进行等价变形，消除模运算的歧义：
对于任意整数X，(X) % m + 1 = k等价于X ≡ k-1 mod m，结合m=256且元素取值为1~256，可推导出：

1. 从Eq1变形得：

   a - b + 3y - x ≡ 3z - 1 mod 256
   

   整理为b关于a的表达式：

   b ≡ a + (x + 1 - 3y - 3z) mod 256
   

   由于元素取值为1~256，用target_b = (a + C1 - 1) % 256 + 1计算目标b值（其中C1 = (x + 1 - 3y - 3z) % 256），自动处理模256后的0对应256的情况。

2. 从Eq2变形得：

   a - c + y ≡ 2z - 1 mod 256
   

   整理为c关于a的表达式：

   c ≡ a + (y + 1 - 2z) mod 256
   

   同理，用target_c = (a + C2 - 1) % 256 + 1计算目标c值（其中C2 = (y + 1 - 2z) % 256）。

优化步骤 #

1. 预处理映射表：建立元素值到对应索引列表的字典，实现O(1)时间查询某值的所有索引。
2. 预计算常数：提前算出C1和C2，避免重复计算。
3. 遍历单个元素推导：对每个a，直接计算对应的target_b和target_c，查询是否存在符合索引唯一性要求的b和c。

优化后代码 #

from collections import defaultdict

# 已知变量（替换为实际值）
x, y, z = ...  
arr = ...      # 长度为101的数组，元素取值1~256
m = 256

# 步骤1：预处理值到索引列表的映射
value_indices = defaultdict(list)
for idx, val in enumerate(arr):
    value_indices[val].append(idx)

# 步骤2：预计算常数项
C1 = (x + 1 - 3 * y - 3 * z) % m
C2 = (y + 1 - 2 * z) % m

# 存储所有符合条件的三元组（索引）
result_triples = []

# 步骤3：遍历每个a的索引和值
for a_idx, a_val in enumerate(arr):
    # 计算目标b值并筛选有效索引
    target_b = (a_val + C1 - 1) % m + 1
    b_candidates = [idx for idx in value_indices.get(target_b, []) if idx != a_idx]
    if not b_candidates:
        continue
    
    # 计算目标c值并筛选有效索引
    target_c = (a_val + C2 - 1) % m + 1
    c_candidates = [idx for idx in value_indices.get(target_c, []) if idx != a_idx]
    if not c_candidates:
        continue
    
    # 收集所有索引不重复的三元组
    for b_idx in b_candidates:
        valid_c_indices = [c_idx for c_idx in c_candidates if c_idx != b_idx]
        for c_idx in valid_c_indices:
            result_triples.append((a_idx, b_idx, c_idx))

# 输出结果
print(f"找到{len(result_triples)}个符合条件的三元组")
print(result_triples)

复杂度分析 #

• 预处理映射表：O(n)
• 遍历每个a：O(n)，每次查询和过滤操作的时间取决于元素重复次数，由于数组长度101远小于元素范围256，平均每个值出现次数不足1次，总复杂度接近O(n)，远低于原O(n²)的复杂度。

内容的提问来源于stack exchange，提问作者Vineet Mangal