Cod sursa(job #578423)

Utilizator Ghdel_RaduGhidel Ghdel_Radu Data 11 aprilie 2011 11:54:33
Problema Frac Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.3 kb
const nmax=200000;pmax=1e14;
var prim:array[1..nmax]of longword;
    n,p,sol:qword;
    k:longword;

procedure citire;
begin
assign(input,'frac.in');reset(input);
readln(n,p);
close(input);
end;

procedure precalc;
var i,j,r:longword;
    v:array[1..nmax]of byte;
begin
k:=0;
for i:=2 to trunc(sqrt(n)) do
 if v[i]=0 then
  begin
  if n mod i=0 then
   begin
   inc(k);
   prim[k]:=i;
   end;
   r:=trunc(sqrt(n)) div i;
   for j:=1 to r do
   v[j*i]:=1;
  end;
end;

function valid(m:qword):boolean;
var i:longword;j,nr:byte;
    prod:qword;rez,fact:int64;
begin
fact:=0;
for i:=1 to 1 shl k-1 do
 begin
 nr:=0;prod:=1;
 for j:=0 to k-1 do if (i shr j)and 1=1 then
  begin
  inc(nr);
  prod:=prod*prim[j+1];
  end;
 if odd(nr) then inc(fact,n div prod) else dec(fact,n div prod);
 end;
rez:=m-fact;
if rez<p then valid:=true else
 if rez=p then begin
               sol:=m;
               end
               else valid:=false;
end;

procedure cautare;
var l,r,m:qword;
begin
l:=1;r:=1 shl 61;
while (l<=r)and(sol=0)do
 begin
 m:=(l+r)shr 1;
 if valid(m) then l:=m+1 else r:=m-1;
 end;
end;

procedure afisare;
begin
assign(output,'frac.out');rewrite(output);
writeln(sol);
close(output);
end;

begin
citire;
precalc;
cautare;
afisare;
end.