题目地址: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
就解方程。
然后就剩下高精度了。。。。