[CSP-J 2022 T2]解密题解
这题可以使用暴力求解，但是因为n的值过大，所以即使拥有单O(kn)O(k\sqrt{n})O(kn )的时间复杂度也只能获得60分，这道题的答案其实是数学的O(k)O(k)O(k)解，推导过程如下
∵(p−1)(q−1)+1=ed∴pq−p−q+1+1=ed∵pq=n∴ed=n−p−q+2∴p+q=n−ed+2=m∴(p+q)2=m2∴p2+2pq+q2=m2∴m=(p+q)2=p+q∴p2−2pq+q2=m2−4pq∴(p−q)2=m2−4pq设c=p−q∴c=m2−4pq=m2−4n=p−q(m2−4pq,m2−4n≥0)∴m+c=2p(p为正整数,所以m+c为偶数)∴q=m−(m+c)/2∵(p-1)(q-1)+1=ed \newline∴pq-p-q+1+1=ed \newline∵pq=n \newline∴ed = n - p-q+2
\newline∴p+q=n-ed+2=m \newline∴(p+q)^2=m^2 \newline∴p^2+2pq+q^2=m^2 \newline∴m = \sqrt{(p+q)^2} = p+q \newline∴p^2-2pq+q^2=m^2-4pq \newline∴(p-q)^2=m^2-4pq \newline设c=p-q \newline∴c = \sqrt{m^2-4pq}=\sqrt{m^2-4n}=p-q(m^2-4pq,m^2-4n≥0) \newline∴m+c=2p(p为正整数,所以m+c为偶数) \newline∴q=m-(m+c)/2
∵(p−1)(q−1)+1=ed∴pq−p−q+1+1=ed∵pq=n∴ed=n−p−q+2∴p+q=n−ed+2=m∴(p+q)2=m2∴p2+2pq+q2=m2∴m=(p+q)2 =p+q∴p2−2pq+q2=m2−4pq∴(p−q)2=m2−4pq设c=p−q∴c=m2−4pq =m2−4n =p−q(m2−4pq,m2−4n≥0)∴m+c=2p(p为正整数,所以m+c为偶数)∴q=m−(m+c)/2
答案就是先输出p、q中的较小值，再输出较大值
可以先写一下，实在写不出来再看代码吧!
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−------------------------------------------−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
