题解：P1001 A+B Problem

给定 $A, B$，计算：

的结果，其中 $|A|, |B| \le 10^9$。

注意到这个式子非常困难，我们先考虑取一些素数 $p$，在模素数意义下的计算，最后再用 CRT 组合起来。

考虑

即

也就是说，如果我们能找到合适的 $a, b$，使得 $\binom a 2 \equiv A \pmod p, \binom b 2 \equiv B \pmod p$，就可以求出答案。

观察

考虑求根公式

解一个二次剩余即可。

一个问题是二次剩余不一定存在，所以随机模数 $p$，并用 Miller-Rabin 算法判断即可。

还有问题是答案可能是负数，我们发现如果答案是负数，则算出来的答案会大于 $2 \times 10^9$，此时将 $A, B$ 同时取负，再计算答案即可。