poj 1811, poj 2429 (pollard_rho算法)
时间：
2015-02-12 21:27:50
阅读：
246
评论：
收藏：
0
[点我收藏+]
poj 1811
题意：
给出一个整数n，判断n是不是素数，如果不是素数，输出最小的质因子。
限制；
2 <= N < 2^54
思路：
miller_rabin算法判素数
pollard_rho算法求质因子
复杂度O(log(n))
poj 2429
题意：
给出两个数的lcm和gcd，求这两个数。
限制：
0 < lcm,gcd < 2^63
思路：
pollard_rho O(log(n))分解质因数。
可以考虑到2^63不同的质因数只有20左右个，而相同的质数不可能分在不同的数里，所以可以暴力。
poj 1811, poj 2429 (pollard_rho算法)
原文：http://blog.csdn.net/whai362/article/details/43767665
