令 \(S(a)=\sum_{i} a_i^2\)

展开 \(c_i\) 式子里的平方，得到 \(c_i=S(a)+S(b)-2\sum_{k}a_kb_{(k+n-i)\bmod n}\)

翻转 \(b\)，令 \(c'_i=c_i-S(a)-S(b)\)，可以得到 \(\text{DFT}(a)\cdot \text{DFT}(b)=\text{DFT}(c')\)，即 \(a=\text{IDFT}(\text{DFT}(c')/\text{DFT}(b))\)

分析一下让 \(c\) 全体减去一个 \(x\) 会对最终得到的 \(a\) 有啥影响

首先 \(\text{DFT}(c)_i=\sum_{j} c_j \omega_n^{ij}\)，当 \(c\) 整体加上一个 \(x\) 时，对于 \(\text{DFT}(c)_i\) 的影响是加上 \(x\times \sum_{j}\omega_n^{ij}\)，注意到当 \(i>0\) 时，\(\sum_{j}\omega_n^{ij}=0\)，即这时候只会对 \(\text{DFT}(c)_0\) 加上 \(n\times x\)

类似的分析，我们最终可以得到让 \(c\) 全体减去一个 \(x\) 会让最终得到的 \(a\) 全体减去 \(\dfrac{x}{\text{DFT(b)[0]}}\)

我们先假设 \(S(a)=0\)，然后把按照上述做法做得到的结果设为 \(a'\)

于是我们可以得到方程：\(\sum_{i} (a'_i-\frac{x}{DFT(b)[0]})^2=x\)

然后就做完了

关于实现：

  1. 可以整个过程在一个存在 \(n\) 次单位根的大模数域下做，对于判断最终结果是否为负数，只要考虑当前这个数距离 \(0\) 和 \(mod\) 哪个更近。
  2. 解方程可以直接求二次剩余，注意到如果存在解，那么一元二次方程的那个 \(\delta=b^2-4ac\) 也肯定存在二次剩余。但是这样可能会解出来多一组在模域下合法的解，但是这个时候这组解的绝对值的最大值肯定会比较大，当大于某个阈值的时候舍去这组解即可。