数据范围……int64解决了……或者qword……

然后就是一个分解，

分解完了，

再加个排列组合的DP，

结果也就出来了……

嗯，回去做做……

Program po;

var n:int64;

o,i,t:longint;

function work(n:int64):longint;

var i,t:longint;

kind:boolean;

begin

t:=0;

kind:=true;

for i:=2 to trunc(sqrt(n)) do

if n mod i=0 then begin

t:=t+work(i);

kind:=false;

end;

t:=t*2;

if kind then inc(t);

work:=t;

end;

{function work2(n:int64):longint;

var

t:int64;

i:longint;

kind:boolean;

begin

kind:=true;

t:=n+1;

for i:=2 to trunc(sqrt(n)) do

if n mod i=0 then begin

if i+work2(i)

分解质因数，但是这个数据太恶心了

质数。。。

water。。。

dp。。。

我也留个名。

这题数据范围太大，怎么做？

var
n:longint;

function gcd(a,b:longint):longint;
begin
if a=0 then gcd:=b
else gcd:=gcd(b mod a,a);
end;

function modular_exponentiation(a,b,n:longint):longint;
var
d,i,k:integer;
bb:array [0..1000] of 0..1;
begin
d:=1;
k:=-1;
while b>=2 do begin
inc(k);
bb[k]:=b mod 2;
b:=b div 2;
end;
inc(k);
bb[k]:=b;
for i:=k downto 0 do begin
d:=(d*d) mod n;
if bb[i]=1 then d:=(d*a) mod n;
end;
modular_exponentiation:=d;
end;

function miller_rabin(n,s:longint):boolean;
var
i,a:longint;
begin
randomize;
for i:=1 to s do begin
a:=random(n-1)+1;
if modular_exponentiation(a,n-1,n)<>1 then begin
miller_rabin:=false;
exit;
end;
end;
miller_rabin:=true;
end;

function pollard_rho(c,n:longint):longint;
var
i,x,y,k,d:longint;
begin
randomize;
i:=1;
x:=random(n);
y:=x;
k:=2;
repeat
inc(i);
d:=gcd(2*n+y-x,n);
if (d>1) and (d<n) then begin
pollard_rho:=d;
exit;
end;
if i=k then begin
y:=x;
k:=k*2;
end;
x:=(x*x+n-c) mod n;
until y=x;
pollard_rho:=n;
end;

procedure rho(n:longint);
var
t:longint;
begin
if miller_rabin(n,2) then writeln(n)
else begin
repeat
t:=pollard_rho(random(n-1)+1,n);
if t<n then begin
rho(t);
rho(n div t);
end;
until t<n;
end;
end;

begin
readln(n);
rho(n);
end.