在whk上咕咕的我终于回来了,这用的是数学方法。

Solution

首先 $(p_i-1)(q_i-1)+1$ 什么也看不出来,先拆个括号,就会变成 $p_i·q_i-p_i-q_i+2$ 这个样子,已知 $p_i·q_i=n_i$ 且 $p_i·q_i-p_i-q_i+2=e_i·d_i$ ,就可以得出来两个东西 $p_i·q_i$ 和 $p_i+q_i$ 。

$p_i+q_i$ 过程:

现在我们得知了 $p_i+q_i$ 和 $p_i·q_i$ ,怎么求出 $p_i,q_i$ 呢?

对,就是课本上的完全平方公式,因为 $(p_i+q_i)^2-(p_i-q_i)^2=4p_i·q_i$ 又知道了 $p_i+q_i$ 和 $p_i·q_i$ ,所以直接反向求出来 $p_i-q_i$ ,就是一个和差问题,非常简单了。如下:

为什么是 $4p_i·q_i$ :

$p_i-q_i$ 过程:

注意,这里还要判断是否有解,如果这个东西的平方根不是整数或者是一个负数,就是无解的。(一个数的平方一定是非负数)

这就解完了,代码先不贴了。