十分厉害的数论提

十分厉害。

\(x,y\in[1,p\times (p-1)]\) 求使得 \(x^y=y^x \bmod p\) 的对数。

首先这个东西不能用原根，阶去分析， 因为 \(x\) 可能大于 \(p\)，这样会产生一个 %p 不容易考虑了。

那只能观察这个定义域限制了。

先改写一下方程 ：\((x\bmod p)^{y\ \bmod p-1}={(y\bmod p)}^{x\ \bmod p-1}\)

然后就非常有意思的是，实际上你知道一个数 \(\bmod p\) 与 \(\bmod p-1\) 当 \(p\in Prime\) 时，能唯一确定这个数。中国剩余。

然后就可以枚举 \(x\bmod=g^a\) 与 \(y=b\) 的 \(a,b\) 这样就能张成一个 \((p-1)\times (p-1)\) 的空间。

然后同样的匹配就好。 \[ \mathrm{tim[i]}=\sum_{a}\sum_{b} [a\times b]\bmod p-1=i \] 答案就是 \(\sum_{i}\mathrm{tim[i]}^2\)。现在模数都是 \(p-1\) 不妨记 \(q=p-1\)。

解方程很简单，我们枚举一个 \(a\times b\) 的 \(a\) 然后看 \(a\) 存在逆元情况计算即可。

\(\mathrm{tim[i]}=\sum\limits_{a} [\gcd(a,q)|i]\gcd(a,q)\) 。

考虑实际含义b多因子是没有任何影响的，具体也可以通过打表看出 \(\mathrm{tim[i]}\) 的值只跟 \(\gcd(i,q)\) 相关，我们可以只计算 \(i\mid q\) 的 \(\mathrm{tim[i]}\) 即可。 \[ \begin{aligned} \mathrm{tim[i]}&=\sum_{a} [\gcd(a,q)|i]\gcd(a,q)\\ &=\sum_{g|i,g|q}g\sum_{a}[\gcd(a,q)=g]\\ &=\sum_{g|i,g|q}g\sum_{tg|q}\mu(t)\sum_{tg|a}1\\ &=\sum_{T|q}q/T\sum_{g|T,g|i}g\mu(T/g)\\ &=\sum_{g|i}\sum_{g|T,T|q}g\mu(T/g)q/T\\ &=\sum_{g|i}\sum_{T|(q/g)}g\mu(T)q/(Tg)=\sum_{g|i}g\varphi(q/g)\\ \end{aligned} \] 现在可以通过枚举因子计算出 \(\mathrm{tim[i]}\) 但是这并不足够。

发现计算答案的区间长度极小。不难想到因子数的限制和区间筛。

因子数 1-r的因子数看成 \(r\ln r\) ,区间的因子数可以看成 \(r\ln r-l\ln l\leq (r-l)\ln r\) 。

因子数也就是 \(1e6\ln 1e6\) 级别的，但是因子的因子数却爆炸了。

考虑 \(g\varphi(q/g)\) 这个东西怎么计算。不难发现事实上，他应该等于 \(q\) 除上一些东西。 这些东西是 \(g\) 不完全拥有的质因子 \(1-\frac{1}{p}\) 。

这样便可以在 \(dfs\) 过程中 \(O(\mathrm{factors})\) 时间计算出来每一个 \(i\) 的值。（因子分开，类似因子个数那么乘起来）

复杂度 \(O((r-l)\ln r)\)。