26 条题解

  • 0
    @ 2009-08-01 13:36:04

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

    然后就是一个分解,

    分解完了,

    再加个排列组合的DP,

    结果也就出来了……

    嗯,回去做做……

  • 0
    @ 2009-08-01 13:12:35

    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)

  • 0
    @ 2009-08-01 12:48:31

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

  • 0
    @ 2009-08-01 11:52:36

    质数。。。

    water。。。

    dp。。。

  • 0
    @ 2009-08-01 12:09:12

    我也留个名。

    这题数据范围太大,怎么做?

  • -1
    @ 2014-05-10 16:28:53

    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.

信息

ID
1606
难度
9
分类
贪心 | 高精度 点击显示
标签
(无)
递交数
340
已通过
13
通过率
4%
被复制
2
上传者