如何枚举无符号64位两序列的交集？求非暴力方案

问题核心条件 #

要找到同时属于两个序列的64位数字P，需满足：

• ( P \equiv 0 \pmod{k} )（是k的倍数）
• ( P = C | S )，其中S是掩码m的子集（即( S & \sim m = 0 )），且已知( C & m = 0 )（C和m无重叠位）
• ( P & \sim(C|m) = 0 )（P的非C、非m位全为0）

等价于求解同余方程：( (C + S) \equiv 0 \pmod{k} )，其中S是m的子集（因C与m无交集，( C+S = C|S )）。

替代枚举方法：基于线性同余方程组求解 #

不用逐个检查k的倍数或m的子集，可通过模k的0-1线性方程组求解直接生成所有符合条件的S，进而得到P，实现高效迭代器。

步骤1：转化为线性方程组

将m的每个置位位视为二进制变量( x_i \in {0,1} )，对应权值为( 2^i )。则S可表示为( S = \sum x_i \cdot 2^i )，代入同余方程得：
[
\sum x_i \cdot (2^i \mod k) \equiv (-C \mod k) \pmod{k}
]
其中( -C \mod k )需调整为非负值（若结果为负则加k）。

步骤2：高斯消元求解方程组

对上述模k的0-1线性方程组进行高斯消元，得到：

• 一个特解( S_0 )：满足方程的某个子集S
• 一组基向量：每个基向量对应一个子集，将特解与任意基向量组合（按位或，因基向量对应不重叠的位组合），可生成所有满足方程的S

步骤3：实现迭代器生成交集元素

基于特解和基向量，迭代器可通过遍历基向量的所有组合（二进制计数器方式），每次生成新的S，再与C按位或得到P。这种方式无需额外检查，直接输出符合条件的交集元素。

示例代码框架（C++） #

#include <vector>
#include <cstdint>

// 预处理：提取m的置位位权值mod k，求解方程组得到特解和基向量
// （此处省略高斯消元具体实现，需根据模k的特性编写）

class IntersectionIterator {
private:
    uint64_t C;
    uint64_t s0; // 特解对应的S值
    std::vector<uint64_t> base_S; // 基向量对应的S值（每个基是m的子集）
    size_t counter;
    size_t max_combinations;

public:
    IntersectionIterator(uint64_t C_, uint64_t s0_, const std::vector<uint64_t>& bases)
        : C(C_), s0(s0_), base_S(bases), counter(0) {
        max_combinations = 1ULL << base_S.size();
    }

    bool hasNext() const {
        return counter < max_combinations;
    }

    uint64_t next() {
        // 计算当前组合对应的S
        uint64_t current_s = s0;
        size_t cnt = counter;
        for (size_t i = 0; i < base_S.size(); ++i) {
            if (cnt & 1) {
                current_s |= base_S[i];
            }
            cnt >>= 1;
        }
        counter++;
        return C | current_s; // C与m无交集，等价于C + current_s
    }
};

优势说明 #

• 预处理仅需一次，后续迭代生成元素的时间复杂度为( O(t) )（t为基向量数量，通常远小于m的置位位数）
• 避免了逐个检查的冗余计算，尤其当k很大或m的子集数量极多时，效率提升显著
• 迭代器按需生成元素，无需预存所有交集结果，节省内存

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