最长异或公共子段

思路

题目给了两个不同的非负整数 ，分别生成两个无限序列 和 （）。要求找到最长的公共连续子段长度 。

"公共连续子段"意味着存在 使得对所有 ，有 ，即：

$$

两边同时异或，等价于：

$$

其中 是个固定值。

关键转化

问题变成：找最大的 ，使得存在 ，对连续 个 值都有 。

取 ，设 ，则条件变为 对连续 个 成立。

当我们选 时，条件变成 。什么时候 呢？恰好是 和 没有公共的 1-bit，即 的时候。

所以问题进一步简化为：最长的连续整数段 ，满足每个数与 按位与为 0。

lowbit 就是答案

设 的最低位的 1 在第 位（即 是 的末尾零的个数）。那么 要求 的第 位为 0。但连续的整数中，第 位每隔 个数就会翻转一次。所以最多有 个连续整数使得第 位为 0，同时更高位的约束也可以通过合理选择 的起始位置来满足。

因此答案就是 的 lowbit，即 。

可以验证所有样例：

  • ，lowbit = 1
  • ，lowbit = 8
  • ，lowbit = 4
  • ，lowbit =

复杂度

  • 时间：，每组测试
  • 空间：

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        long long x, y;
        scanf("%lld%lld", &x, &y);
        long long d = x ^ y;
        printf("%lld\n", d & (-d));
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            long x = sc.nextLong();
            long y = sc.nextLong();
            long d = x ^ y;
            System.out.println(d & (-d));
        }
    }
}

import sys
input = sys.stdin.readline

T = int(input())
out = []
for _ in range(T):
    x, y = map(int, input().split())
    d = x ^ y
    out.append(str(d & (-d)))
print('\n'.join(out))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', (line) => lines.push(line.trim()));
rl.on('close', () => {
    let idx = 0;
    const T = parseInt(lines[idx++]);
    const res = [];
    for (let i = 0; i < T; i++) {
        const parts = lines[idx++].split(' ').map(BigInt);
        const d = parts[0] ^ parts[1];
        res.push((d & (-d)).toString());
    }
    console.log(res.join('\n'));
});