计数

当n等于1时，整个集合中只有数字0.
当n大等于2时，我们可以枚举1到r中所有数，并使用一个数组记录l到r的每个数是否在集合中。
由于空间限制的原因，本题需要使用bitset或者手写压位。

永恒游戏

有一个定理保证，对于一个固定的初始局面，不论怎么操作，要么可以无限操作下去，要么在相同步数之后停在相同的局面上。所以只需要模拟100000次即可知道本题答案。

定理的证明可以在以下论文中找到 http://www.cs.elte.hu/~lovasz/morepapers/chips.pdf （定理1.1）

天下无骰

首先我们考虑一个简单的情形：
如果我们将整棵决策树分成等概率的k个叶子节点，且k大等于(n - 1) ^ 2，那么我们可以简单地将这些节点分成n份，其中(n - 1)份的概率都相同，另一份的概率比它们都小。显然我们可以轻松地使用一枚硬币将那(n - 1)份的概率降到1 / n， 这样我们就得到了答案。
故我们可以使用1 / 2的硬币得到上文所提到的的决策树，然后使用另一枚硬币搞定这件事。很容易的发现，在这种构造方法中，分母的值小于10^9。