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

Solution

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

pi+qip_i+q_i 过程：

\begin{equation*} \begin{aligned} p_i·q_i-p_i-q_i+2 &= e_i·d_i \\ p_i+q_i &= -(e_i·d_i-p_i·q_i+2) \\ &= p_i·q_i-e_i·d_i-2 \\ &= n_i-e_i·d_i-2 \end{aligned} \end{equation*}

现在我们得知了 pi+qip_i+q_i 和 pi⋅qip_i·q_i ，怎么求出 pi,qip_i,q_i 呢？

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

为什么是 4pi⋅qi4p_i·q_i ：

\begin{equation*} \begin{aligned} (p_i+q_i)^2-(p_i-q_i)^2 &= {p_i}^2+2p_i·q_i+{q_i}^2-({p_i}^2-2p_i·q_i+{q_i}^2) \\ &= {p_i}^2+2p_i·q_i+{q_i}^2-{p_i}^2+2p_i·q_i-{q_i}^2 \\ &= 4p_i·q_i \end{aligned} \end{equation*}

pi−qip_i-q_i 过程：

\begin{equation*} \begin{aligned} (p_i+q_i)^2-(p_i-q_i)^2 &= 4p_i·q_i \\ (p_i+q_i)^2-4p_i·q_i &= (p_i-q_i)^2 \\ (p_i-q_i)^2 &= (p_i+q_i)^2-4p_i·q_i \\ \end{aligned} \end{equation*}

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

\begin{equation*} \begin{aligned} p_i-q_i &= \sqrt{(p_i+q_i)^2-4p_i·q_i} \\ &= \sqrt{(p_i+q_i)^2-4n_i} \end{aligned} \end{equation*}

\begin{equation*} \begin{aligned} p_i &= \frac{p_i+q_i+(p_i-q_i)}{2} \\ q_i &= p_i+q_i-p_i \end{aligned} \end{equation*}

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