Discussion @ 1204. Idempotents @ Timus Online Judge

gymn28_Kostya // Problem 1204. Idempotents 4 Apr 2003 18:38

Stefan Ciobaca Can someone explain this problem to me? [2] // Problem 1204. Idempotents 22 Mar 2002 03:41

Rostislav PLS! Can N be prime? [1] // Problem 1204. Idempotents 15 Apr 2002 22:32

wuwuwu why? 5^5=5 (mod 6) !! [1] // Problem 1204. Idempotents 10 Apr 2002 13:19

gaozhenwei My program is "Limit Time",Who can help me! [5] // Problem 1204. Idempotents 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.

Komandos Re: My program is "Limit Time",Who can help me! [4] // Problem 1204. Idempotents 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.

gaozhenwei Re: My program is "Limit Time",Who can help me! // Problem 1204. Idempotents 7 Apr 2002 09:28

I don't understand!
Can you tell me clear?
Thank you!!!

gaozhenwei Re: My program is "Limit Time",Who can help me! [2] // Problem 1204. Idempotents 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:

Komandos Re: My program is "Limit Time",Who can help me! [1] // Problem 1204. Idempotents 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.

gaozhenwei Re: My program is "Limit Time",Who can help me! // Problem 1204. Idempotents 8 Apr 2002 14:27

Thank you very much!!!!!!
I got AC!!!!!!!1

Blue cat Oh!I lost myself,my confidence in this unfortunate problem.Maybe I foget all of my resplendence in the past.What a shame! [2] // Problem 1204. Idempotents 19 Mar 2002 16:28

Blue cat Yes,I know all this.My algorithm is O(sqrt(n)),but I got Time Limited exceeded.The program uses only 1.5 sec at my computer when K=1000 and the dataset is random.It will cost also O(sqrt(n)) to get p [3] // Problem 1204. Idempotents 19 Mar 2002 15:46

Miguel Angel Someone could help me with the TL?? (+) [1] // Problem 1204. Idempotents 20 Mar 2002 10:40

Blue cat After all,thanks to all those who help me. // Problem 1204. Idempotents 19 Mar 2002 16:00

Blue cat Can anybody help me with P1204?If so,please send message to "flyingbluecat@hotmail.com". [1] // Problem 1204. Idempotents 19 Mar 2002 14:18

Discussion of Problem 1204. Idempotents