DAP AN THI HSG TPHCM NAM 2011 BAI 2

{ Doc file co chua n
Neu n=1 thi M(1)=1
Neu cac uoc so nguyen to cua n co tu 2 so giong nhau thi xuat M(n)=0 m(45)=3x3x5=45
Con lai M(n)=(-1)^p cac uoc so nguyen to khac nhau m(34)=1 vi 2x14=34, M(78)= -1 vi 2x3x13=78}
program tt;
uses crt;
var unt:array[1..100] of integer;
d,k,i,j,n,t:integer;
fi,fo:text;

function ktnt(x: integer):boolean;
begin
ktnt:=true;
for k:=2 to x div 2 do
if x mod k=0 then ktnt:=false;
end;
begin
clrscr;
{write(`Nhap n:`); readln(n);}
assign(fi,`d:mobius.inp`);
assign(fo,`d:mobius.out`);
reset(fi);
read(fi,n);
t:=n;
j:=1;
for i:=2 to n div 2 do
begin

if (ktnt(i)=true) and (t mod i=0) then
begin

repeat
unt[j]:=i;
j:=j+1;
t:=t div i;
until (t mod i<>0);
end;
end;
d:=1;
for i:=1 to j-1 do
begin
write(unt[i],` `);

if unt[i]=unt[i+1] then d:=d+1;

end;
writeln;
rewrite(fo);
if n=1 then writeln(fo,1);
if d>1 then writeln(fo,0)
else if (j-1) mod 2=0 then
write(fo,1)
else
write(fo,-1);
close(fi);
close(fo);
readln;
end.