互娱笔试T3小记

互娱笔试 T3

题目描述：给定方程 ，给定 ，求字典序最小的整数四元组 使方程成立，且 ，若不存在，输出 -1。

范围约定：。 时空限制：3s，131MB。

背景：拿到此题时我还有 1h 的时间，前两题迅速切掉，感觉一路顺风顺水。

思路：看到范围知道暴力是立方级别的一定会超时，所以考虑优化。

我们考虑只遍历 ，则设 ，如果能在常数或者对数时间复杂度内判断出是否存在合法的 能够满足

即可。若 ，显然不存在，于是我们接下来只考虑 的情况。

若 ，易知一定不存在合法的 ，下面考虑 的情况。

等式两边同除 ，有 ，其中

于是有 ，由裴蜀定理可知，若 没有 的限制，则一定存在这样的 ，使得上式成立。

解决方案很简单，先凑出 ，再令

即可。关于如何求解这样的 ，逆元就好了。

由费马小定理，取 为 在模 意义下的逆元，快速幂即可，时间复杂度 ，即

则

于是

但这个时候的 是负数，我们尝试对原方程进行变型，化为

于是只需判断是否存在这样的 ，满足不等式组

于是

可以看到， 以 是否大于 为界分为两种， 以 是否大于 为界分为两种。

最后只需判断是否满足 且在 中存在整数即可。若不满足输出 -1，否则找到最大的合法 ，带入求解 即可（为什么是最大的？因为字典序要尽量小， 尽量小）。

整体复杂度 ，3s 足以通过。

尾记：是一道很好的题，值得记录。但很难想象本人考场上前面全部推了出来，到解不等式链的时候化简出错导致功亏一篑。