传送门

*2300

牛逼打表题。

这个式子很不可思议,让人无从下手。选择打表找规律。

由于 \(2\nmid X\)\(5\nmid x\) 这些数我们可以跳过

通过打表前 \(10000\) 的数,我们发现似乎没有重复的。

继续打表 \(1000000\) 也没有重复的。

直接大胆猜想,\(10^9\) 内的 \(n^n\) 是构成无冲突哈希映射的。

再打一下 \(10^8\) 的情况,发现也是成立的。

这么好用的性质?反正也不会证明

先把前 \(10^6\) 位的给处理好,但是怎么找到下一个也满足同余的呢?

继续打表,发现就是只要是这个数为结尾就行。

这直接暴做就好了,打个表再加数即可。

时间复杂度 \(O(10^6\log 10^6 + 100Q)\)

不看题解根本不会,我好菜()