有人做了昨晚的 Codeforces div2 吗？

[huglight]

想问下为什么 D 题只要不为 0 的数大于 128 个，输出的最小环节点数就为 3 呢？

[DaCong]

其实并不需要大于 128，大于 120 即可。
首先，认识到一点：如果任何一个 bit 上的 1 多于 3 个，那么答案为 3，因为这已经是最短的环了。
而题目的数据范围是 10^18，59<log(10^18)<60，因此一个数最多要 60 个 bit 来储存。
根据抽屉原理，如果非零的不同数字多于 2*60=120 个，则至少有一个 bit 上是有大于等于 3 个的 1。
至于为什么很多人用了 64*2，是因为他们懒得精确去算 log(10^18)，而是用了 64 位整数的上界。

[huglight]

@DaCong 非常感谢~~还是自己太菜了，不了解组合数学