首先让我们一步步分析问题，题目是让我们求得一个p和一个q，使得p*q=n，e*d=(p-1)(q-1)+1，那么首先我们想到的思路肯定是暴力枚举。从上往下枚举，直到找到第一个符合条件的p和q，代码如下： 这段代码的复杂度很明显是 O(n2)O(n^{2})O(n2) ，那么可以得到多少分呢？经过测试，60分。 在考场上这种代码只适用于追求不高的人。那些追求高的人应该怎么样呢？首先这种有二分性的题目第一眼就应该看出应该是要用二分来解决。并不需要修改太多，只需要把暴力线性枚举改成二分答案就行了。代码如下： 这段代码复杂度是 O(nlogn)O(nlogn)O(nlogn) 虽然可以得到100分，但是还有 O(n)O(n)O(n) 的算法！这完全就是考验数学，本蒟蒻也不太懂，下面的这个代码参考了 @唱跳坤 的代码，如有侵权，立马删除。 至此，以达到最优复杂度，无法继续优化，结束。

以下为数学表达法 由题得n=pq,ed=pq-p-q+2(完全平方公式) 把n=pq带入ed,得 ed=n-p-q+2移项 ed-n-2=-q-p同成-1 n-ed+2=p+q 设n-ed+2为m(与下面程序相对应) 即m=q+p 则m2=q2+2qp+p^2同减4n m2-4n=q2+2qp+p^2-4qp m2-4n=(q-p)2 设m^2-4n为op 由于平方的非负性 所以op一定>=0否则无解 求op平方根up 若up为小数则不符合题意舍 现在整理一下 up=q-p m=q+p 所以(up+m)/2为q 如果(up+m)/2为小数则不符合题意 p就是m-q啦 最后先输出小的在输出大的就ok啦

感谢唐老师！！！

十年OJ一场空,不开LONG LONG见祖宗！ AC代码 欢迎加入团队

这个题有两种做法，一种是解方程，一种是二分，我们用二分来解这道题。 其实就是二分答案，炒鸡煎蛋，直接给代码：