# P進XOR解説
writer: qLethon, tester: ferin
### 解法

* 2: $n$を$4$で割って余った後半部分のXORを取る
* 2以外: $n$を$P$で割って余った後半部分のXORを取る

### 証明
2は$n, n + 1, n + 2, n + 3$のXORを取ると0になるのは有名．

#### $3$以上の場合
P進で表した時の1桁目は$0, 1, 2, \dots, P - 1$の繰り返し．その和は$\sum_{k = 0}^{P - 1} k = \frac{P(P - 1)}{2}$となり，$P$は奇数であるため，これは$P$の倍数．よって，$P$回繰り返すと0になる．
1桁目以外は，同じ数が$P$の冪乗回繰り返されるため，当然$P$の倍数．よって，$P$回繰り返すと0になる．

### コメント
$0$になる周期が偶数の場合は$2N$、奇数の場合は$N$になって一般の場合にも解ける。$2N$で十分早いので、すべて$2N$でやると実装が楽。

### その他
FA: kotatsugame 08:17