CSP-J2022 T2 解密

在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$ 过程：

$$\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*}$$

现在我们得知了 $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$ ：

$$\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*}$$

$p_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*}$$

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