寻找满足位掩码约束条件的64位乘法因子

问题定义 #

给定一组索引集合 {i₀, i₁, ..., iₙ}、一组规模相同的子集掩码集合 {s₀, s₁, ..., sₙ}，以及一个64位超集掩码 mask，需要找到一个64位整数因子 p，使得对任意索引 i，满足：

((p * i) & mask) == s_i

所有掩码和因子均为64位宽度，以下是8位场景的示例：

mask = 00111000         ((p * index) & mask) == subset
index=3 sub=00010000 => ((p * 3) & mask) == 00010000
index=5 sub=00100000 => ((p * 5) & mask) == 00100000

注：所有子集掩码均为超集掩码的子集，不同索引可能对应相同子集，求解时可忽略该约束。

当前解法的困境 #

目前采用随机枚举因子并验证的暴力法，但该方法时间复杂度为 O(2⁶⁴)，常数因子极大，即便仅7组索引-子集对也无法找到有效因子。

已尝试的分析思路 #

从乘法结果角度拆解，以8位为例（用a、b、c等表示乘法结果对应位是否置1）：

P * Index = 2⁰*a + 2¹*b + 2²*c + 2³*d + 2⁴*e + 2⁵*f + 2⁶*g + 2⁷*h
P = (1a + 2b + 4c + 8d + 16e + 32f + 64g + 128h) / Index

要求P为整数，以Index=5为例取模推导：

P = (1a + 2b + 4c + 3d + 1e + 2f + 4g + 3h) / 5
P = (1(a+e) + 2(b+f) + 4(c+g) + 3(d+h)) / 5

由此可知，满足上述系数加权和模5为0的位掩码对应有效P*Index，可通过除法得到P，但该思路无法扩展至多组索引-子集对的场景。

需求 #

需要找到一种可扩展的算法，能够处理6至4096组索引-子集对（实际更接近下限），高效求解符合约束的64位因子p。

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