给定两个非负整数数组 和 。
定义 。换句话说, 是数组 中所有满足 与 的按位异或结果不超过 的下标 的集合。
请求出最小的数字 ,使得可以将数组 中的元素染成 种颜色,且满足:如果 与 相交,则 和 必须被染成不同的颜色。
换言之,需要找到 ,使得 ,并且如果 ,则 。
提醒一下,两个非负整数的按位“异或”(,xor)定义如下:将两个数写作二进制形式,结果的第 个二进制位为 1,当且仅当两个参数中恰好有一个在该位为 1。例如,。该操作在所有现代编程语言中都有实现,在 C++、Java 和 Python 中写作 ^,在 Pascal 中写作 xor。