POJ 3892 RSA Factorization

时间:2022-05-20 18:19:47

题目地址:http://poj.org/problem?id=3892

题目大意:RSA分解。

这儿的N比较大,要用高精度,如果一般的肯定分解不了,但是这儿有一个限制

|q-kp|<=100000

解题报告:

假设q-kp=V

那么q=kp+V

代入n=pq

n=p*(kp+V)

k*p*p+V*p-n=0

解这个方程即可。

在枚举V的时候

判别式=V*V+4kn

我们可以先计算出一个最大的值T

T*T<=4kn

然后枚举V

如果V*V+4kn>T*T

那么T++

如果V*V+4kn<T*T

那么V++

如果V*V+4kn==T*T

就解方程。

然后就剩下高精度了。。。。