题解：P1001 A+B Problem

· · 题解

题意描述

给定 A, B，计算：

A + B

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

解法说明

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

考虑

ab = \binom {a + b} 2 - \binom a 2 - \binom b 2

即

\binom a 2 + \binom b 2 = \binom {a + b} 2 - ab

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

观察

\binom a 2 = \frac 1 2 a^2 - \frac 1 2 a \equiv A \pmod p

考虑求根公式

a \equiv \frac 1 2 \pm \sqrt {2A + \frac 1 4} \pmod p

解一个二次剩余即可。

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

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