牛客挑战赛40

¶B

给定1e6个随机生成的数,多次询问,给定y,问是否存在一个数x满足x^y在二进制下1的个数<=3

¶做法

因为最多只有3个二进制位不同,考虑将二进制每16位分成4组,满足条件的x与y一定在某一组中的16位完全相同,所以查找该组中的数,又由于数字随机,每次查找的次数期望为$4*(2^{20} / 2^{16})$