CSP 2022J 解密 题解

首先分析题目

对于给定的 $n$，$e$，$d$，询问是否存在一组正整数 $p$，$q$ 满足 $pq=n$ 且 $(p-1)(q-1)+1=ed$。

S.1

考虑暴力。

枚举每组 $pq=n$，检查是否满足 $(p-1)(q-1)+1=ed$。

时间复杂度 $O(k\sqrt{n})$，预计20pts（但实际上40pts）。

S.2（正解）

注意到 $n$ 的范围特别大，考虑分析题目的式子。

$$(p-1)(q-1)+1=ed$$

$$pq-p-q+2=ed$$

$$n-p-q+2=ed$$

$$n-ed+2=p+q$$

令 $m=n-ed+2$。

结合上面的 $pq=n$，注意到这是一个方程。

尝试换元，得到一元二次方程 $p^2-mp+n=0$，只需检验两个根是否都为正整数即可。

时间复杂度 $O(k)$。预计100pts。