本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
题目链接：HDU3864
正解：$Pollard-rho$
解题报告：
$Pollard-rho$算法模板题。
考虑对于一个数$n$，我们有一个$n$以内的数对$(x,y)$，若$gcd(x-y,n)!=1$，那么显然找到了一个$n$的因数$g$，递归往下做下去，分别分解质因子即可。
这个做法的期望次数会很少，可以想想生日悖论。
具体做法就是构造一个序列$x_i$，$x_i=x_{i-1}^2+c$，$x_0$、$c$均为$n$以内不为$0$的随机数，我们就这样做下去，$y$就取$2$的次幂，$x$单增，直到找到为止。
发现有可能如果$x_0$、$c$不好的话可能无解（出现环），需要多随几次，环的判断就是$x$、$y$某次突然相等了。
//It is made by ljh2000
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
#include <bitset>
using namespace std;
typedef long long LL;
typedef long double LB;
typedef complex<double> C;
const double pi = acos(-1);
LL n;
vector<LL>w;
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}
inline LL gcd(LL x,LL y){ if(y==0) return x; return gcd(y,x%y); }
inline LL mul(LL x,LL y,LL mod){
LL r=0;
while(y>0) {
if(y&1) r+=x,r%=mod;
x+=x; x%=mod;
y>>=1;
}
return r;
}
inline LL fast_pow(LL x,LL y,LL mod){
LL r=1;
while(y>0) {
if(y&1) r=mul(r,x,mod);
x=mul(x,x,mod);
y>>=1;
}
return r;
}
inline int MillerRabin(LL n){
if(n==1) return 0; if(n==2) return 1; if(!(n&1)) return 0;
LL aa=n-1,k=0,bb,lin,cc; while(!(aa&1)) aa>>=1,k++; int T=5;
while(T--) {
bb=rand()%(n-1)+1; cc=fast_pow(bb,aa,n);
for(LL i=1;i<=k;i++) {
lin=mul(cc,cc,n);
if(lin==1 && cc!=1 && cc!=n-1) return 0;
cc=lin;
}
if(cc!=1) return 0;
}
return 1;
}
inline LL nex(LL x,LL c,LL n){
return (mul(x,x,n)+c)%n;
}
inline void pollardrho(LL n){
while(!(n&1)) n>>=1,w.push_back(2); if(n==1) return ;
if(MillerRabin(n)) { w.push_back(n); return ; }
LL x=rand()%(n-1)+1,y=x,c=rand()%(n-1)+1,g;
for(LL i=1,j=1;;i++) {
x=nex(x,c,n);
g=gcd(abs(x-y),n);
if(x==y) x=rand()%(n-1)+1,y=x,c=rand()%(n-1)+1,i=0,j=1;
if(g>1 && g<n) break;
if(i==j) j<<=1,y=x;
}
pollardrho(g); pollardrho(n/g);
}
inline void work(){
srand(time(NULL));
while(scanf("%lld",&n)!=EOF) {
if(n==1){ cout<<"is not a D_num"<<endl; continue; }
w.clear();
pollardrho(n);
int t=w.size();
if(t!=2&&t!=3){ cout<<"is not a D_num"<<endl; continue; }
sort(w.begin(),w.end());
if(t==2) {
if(w[0]!=w[1]) cout<<w[0]<<" "<<w[1]<<" "<<n<<endl;
else cout<<"is not a D_num"<<endl;
}
else {
if(w[0]==w[1] && w[1]==w[2]) cout<<w[0]<<" "<<w[0]*w[0]<<" "<<n<<endl;
else cout<<"is not a D_num"<<endl;
}
}
}
int main()
{
work();
return 0;
}
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。