ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1204. Idempotents

My program is "Limit Time",Who can help me!
Posted by gaozhenwei 4 Apr 2002 16:03
var n,m,t,i,j,c1,c2,q:longint;
    p:array[0..3500] of longint;
    ok:boolean;
begin
 read(m);
 p[0]:=2;t:=0;
 for i:=3 to trunc(sqrt(1000000000)) do
 begin
  ok:=true;
  for j:=2 to trunc(sqrt(i)) do
   if i mod j=0 then
   begin
    ok:=false;break;
   end;
  if ok then
  begin
   inc(t);p[t]:=i;
  end;
 end;
 for i:=1 to m do
 begin
  read(n);
  for j:=0 to t do
  begin
   if n mod p[j]=0 then
   begin
    c1:=p[j];c2:=n div p[j];break;
   end
  end;
  write(0,' ',1,' ');q:=1;
  while q*c2 mod c1<>1 do inc(q);
  if q*c2>n div 2 then
   writeln(n-q*c2+1,' ',q*c2)
    else writeln(q*c2,' ',n-q*c2+1);
 end;
end.
Re: My program is "Limit Time",Who can help me!
Posted by Komandos 6 Apr 2002 13:53
You should use Euclid algorithm to solve equation c1*x=1 (mod c2).
Your program execute
   while q*c2 mod c1<>1 do inc(q);
too much time.
Re: My program is "Limit Time",Who can help me!
Posted by gaozhenwei 7 Apr 2002 09:28
I don't understand!
Can you tell me clear?
Thank you!!!
Re: My program is "Limit Time",Who can help me!
Posted by gaozhenwei 7 Apr 2002 09:31
My program is here:
var n,m,t,i,j,c1,c2,q,o:longint;
    p:array[0..3500] of longint;
    ok:boolean;
begin
 read(m);
 p[0]:=2;t:=0;
 for i:=3 to trunc(sqrt(1000000000)) do
 begin
  ok:=true;
  for j:=2 to trunc(sqrt(i)) do
   if i mod j=0 then
   begin
    ok:=false;break;
   end;
  if ok then
  begin
   inc(t);p[t]:=i;
  end;
 end;
 for i:=1 to m do
 begin
  read(n);
  for j:=0 to t do
  begin
   if n mod p[j]=0 then
   begin
    c1:=p[j];c2:=n div p[j];break;
   end
  end;
  write(0,' ',1,' ');q:=1;
  if c2 mod c1=1 then q:=1
   else begin
         o:=1+c1;
         while o mod (c2 mod c1)<>0 do o:=o+c1;
         q:=o div (c2 mod c1);
        end;
  if q*c2>n div 2 then
   writeln(n-q*c2+1,' ',q*c2)
    else writeln(q*c2,' ',n-q*c2+1);
 end;
end.ogram is here:
Re: My program is "Limit Time",Who can help me!
Posted by Komandos 7 Apr 2002 21:11
var k,p,q,sqrtn,i,j,n:longint;
    b:array [1..1000] of longint;
    x,y:longint;
    prost:array [1..5000]of longint;
    flag:boolean;

procedure sol(p,q:longint;var x,y:longint);
{This is implementation of Euclid algorithm.
 After sol(p,q,x,y) you get px-qy=1}
var a,b:longint;
begin
 if p=1 then begin
    x:=1;
    y:=0;
    exit;
 end;
 if q=1 then begin
    x:=1;
    y:=p-1;
    exit;
 end;

 if p>q then begin
    sol(p mod q,q,a,b);
    x:=a;
    y:=(b+a*(p div q));
 end;
 if q>p then begin
    sol(p,q mod p,a,b);
    y:=b;
    x:=(a+b*(q div p));
 end;
end;

begin

  prost[1]:=2;
  prost[2]:=3;
  prost[3]:=5;
  k:=3;
  for i:=7 to 40000 do
   begin
    flag:=true;
    for j:=1 to k do begin
      if i mod prost[j]=0 then begin
         flag:=false;
         break;
      end;
    end;
    if flag then begin
       k:=k+1;
       prost[k]:=i;
    end;
   end;

  read(n);
  for i:=1 to n do
    read(b[i]);

  for i:=1 to n do begin

    sqrtn:=round(sqrt(b[i]));
    for j:=1 to k do begin
      if b[i] mod prost[j]=0 then
         break;
    end;
    p:=prost[j];
    q:=b[i] div p;

    if p<>q then begin
       sol(p,q,x,y);

       write(0,' ',1,' ');

       if x<=q div 2 then
          writeln(p*x,' ',p*q-p*x+1)
       else
          writeln(p*q-p*x+1,' ',p*x);
    end
    else begin
       writeln(0,' ',1,' ');
    end;
  end;
end.
Re: My program is "Limit Time",Who can help me!
Posted by gaozhenwei 8 Apr 2002 14:27
Thank you very much!!!!!!
I got AC!!!!!!!1