一种特殊的模意义下多元高次方程的解法

省流：对于一个多元的 $n$ 次齐次多项式减去一个 $n - 1$ 次的多元齐次多项式等于常数，有一种简单的 $O(\sqrt {Pm}\times Q)$ ，复杂度的做法（$m$ 为多项式中每项的元数和，$Q$ 是快速幂复杂度）。

例如本算法可以解决如下问题：

首先考虑如何求出若干的 $C = 0$ 的解：

随机 $r_1, r_2$，我们另 $y = r_1x, z = r_2x$，那么我们可以发现等式可以形如 $Ax^{1000000}$ = $Bx^{999999}$，取 $x = \dfrac B A$ 即可。

假设我们现在得到了 $C = 0$ 的解，其中左式和右式均等于 $k$。

那么假设 $xyz$ 同时乘上 $R$，则此时两式差为 $k(R^{1000000}-R^{999999})$。

假设我们现在有若干个 $C = 0$ 的解和若干个 $(R^{1000000}-R^{999999})$，那么我们只要找到两个乘起来 $=C$ 的一组解即可。

所以我们将随机若干 $C = 0$ 的解存入哈希表，然后随机 $R$ 寻找 $\dfrac C {(R^{1000000}-R^{999999})}$ 是否在哈希表中即可。

推广上述做法：

然后求 $C = 0$ 的解，我们就先随机若干个 $r_2,r_3...r_t$，表示 $x_a = r_ax_1$，那么此时解 $C = 0$ 等价于原式形如 $Ax^{1000000} = Bx^{999999}$，取 $x=\dfrac B A$，并将解存入哈希表中。

然后我们随机若干 $R$，并检验哈希表中是否存储了 $\dfrac C {R^n - R^{n-1}}$，如果有则将每个数乘上 $R$ 作为结果返回。

假设第一步去了 $s$ 个解，那么第二步期望要 $O(\dfrac P S)$ 步。

即快速幂次数为为 $O(sm+\dfrac P s)$，取 $s = \sqrt {\dfrac P m}$ 得到复杂度 $O(\sqrt{Pm}\times Q)$，$Q$ 为快速幂复杂度（说不定可以省去）。