noip2012最终征途.pdf

NOIP2012 最终征途
NOIP2012NOIP2012 最终征途最终征途
得到与失去，只有时间才能证明。
成功与失败，只有历史才能仲裁。
亟隐 Slack
NOIP2012 最终征途
【数论】

function gcd(x,y:longint):longint;
begin
if y=0 then exit(x) else exit(gcd(y,x mod y));
end;

function prime(x:longint):boolean;
var i:longint;
begin
if x=1 then exit(false);
for i:=2 to trunc(sqrt(x)) do if x mod i=0 then exit(false);
exit(true);
end;

procedure prime;
begin
fillchar(bool,sizeof(bool),true);
for i:=2 to trunc(sqrt(n)) do if bool[i] then
begin
j:=i;
while j+i<=n do
begin
j:=j+i; bool[j]:=false;
end;
end;
for i:=2 to n do if bool[i] then writeln(i);
end;

function power(a,p,t:longint):int 64;
begin
if p=0 then exit(1);
a:=a mod t;
power:=power(a,p shr 1,t);
power:=power*power mod t;
if p and 1=1 then power:=(power*a) mod t;
end;
Rabbin 判断素数
function Miller_Rabbin(t:longint):boolean;
begin
for i:=1 to 32 do
begin
m:=random(t-2)+1;
if power(m,t-1,t)<>1 then exit(false);
end;
exit(true);
end;

procedure deal;
begin
i:=2; sum:=0;
while i<=n do
begin
if n mod i=0 then
begin
inc(sum); f[sum]:=i;
while n mod i=0 do n:=n div i;
end;
inc(i);
end;
for i:=1 to sum do write(f[i],' ');
end;

令 h(0)=1,h(1)=1,h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)
h(n)=h(n-1)*(4*n-2)/(n+1);
h(n)=C(2n,n)/(n+1) (n=1,2,3,...)
h(n)=c(2n,n)-c(2n,n+1)(n=1,2,3,...)

(0)+f⑴+f⑵+…+f(n)=f(n+2)-1.
⑴+f⑶+f⑸+…+f(2n-1)=f(2n).
⑵+f⑷+f⑹+…+f(2n) =