题解：P12855 [NERC 2020 Online] Find a Square

littlez_meow · 2025-06-25 11:57:00 · 题解

似乎只能分解质因数。直接分解质因数是 O(n^{\frac 7 4})，显然跑不了。

那就要分析 P(n) 的性质。感觉起来这个问题可能稍微比分解质因数弱一点，但是没有弱特别多，所以应该不太能 O(\operatorname{polylog}(n))。非筛法的数论题中常见的复杂度还有 \dfrac 1 3 次方和 \dfrac 1 4 次方，但是这个和 \dfrac 1 4 次方的分解质因数与最小原根看起来没什么关系。那初步判断可能就是 O(P(n)^{\frac 1 3}\operatorname{polylog}(n))。

常见的 \dfrac 1 3 的算法是先把小于等于 \dfrac 1 3 次方的质数除掉，剩下的至多为两个质数相乘。我们也尝试往这个方向靠。

接下来我们把 P 看成一个数组，称把 P(x) 除掉 i 表示若 i|P(x) 则 P(x)\leftarrow\dfrac{P(x)}i，否则 P(x) 不变。

对于某个质数 p，若 \gcd(2a,p)=1，那么同余方程 P(x)\equiv 0\pmod p 至多只有两个解 2ax\equiv-b\pm\sqrt{b^2-4ac}\pmod p，其中根号可以用 cipolla 算法来算二次剩余求。解出 x 后我们就知道有哪些 i\in[0,n-1] 满足 P(i)\equiv 0\pmod p，它们满足 i\equiv x\pmod p，一共只有 \lfloor\dfrac n p\rfloor 个。

那么从小到大枚举质数 p，一直枚举到 \sqrt[3]{P(n-1)}。若 \gcd(p,2a)\neq 1，就遍历每个 P(i) 把 p 除掉。否则就解出 P(x)\equiv 0\pmod p 然后把满足 i\equiv x\pmod p 的 P(i) 中除掉 p。这一部分的时间复杂度是 O(n\log n)。

把所有质数都这样处理过一遍后，先把 P 中剩下的平方数统计进答案并设为 1。P 数组中剩下的元素要么是 1，要么是质数 p，要么是两个不同的质数之积 pq。能对答案造成贡献的质数至少要能整除 P 中两个数。

考虑 P(x) 和 P(y) 一开始的 \gcd。我们有 \gcd(P(x),P(y))=\gcd(P(x),a(x^2-y^2)+b(x-y))=\gcd(P(x),(x-y)(a(x+y)+b))。也就是说，至少能整除两个 P 中元素的质数 p 要么是一个 <n 的数的因数，要么是一个形如 ax+b,x<2n 的数的因数。