(p-1)(q-1) is euler function value of n.

This problem involves number theory???

What's wrong with me (or with this test)?
Usually test #1 is the example. I don't see where the problem could come form.
I know there were other people getting TL, could you tell what's the problem.

I got AC http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=10161&courseid=0, but here I got WA1. Why???

I wonder why I'm getting either TL or Crash on the test #1. Complexity of my approach is K*sqrt(N)*log(N)  - more than enough! About crash - bounds of my array is ok, I never divide by zero - something else? Very strange. Please,somebody give some tests.

Edited by author 28.04.2011 10:32

Edited by author 28.04.2011 10:32

{$N+,E-}
program tmp2;
{$APPTYPE CONSOLE}
uses
  SysUtils;
var i,k,j,p,q,d:integer;
    n,e,c:int64;
function pow1(a,k:int64):int64;
var b:int64;
begin
  b:=1;
  while k>0 do
      if k mod 2 = 0 then
        begin
          k:=k div 2;
          a:=a*a;
        end
      else
        begin
          dec(k);
          b:=b*a;
        end;
  pow1:=b;
end;
function powmod(a,k,n:int64):int64;
var b:int64;
begin
  b:=1;
  while k>0 do
    if k mod 2 = 0 then
      begin
        k:=k div 2;
        a:=(a*a) mod n;
      end
    else
      begin
        dec(k);
        b:=(b*a) mod n;
      end;
  powmod:=b;
end;
procedure factor(n:integer);
var d:integer;
begin
  for d:=2 to trunc(sqrt(n)) do
    if n mod d =0 then
      begin
        p:=d;
        q:=n div d;
        exit;
      end;
end;
begin
  { TODO -oUser -cConsole Main : Insert code here }
{  reset(input,'data.in');
  rewrite(output,'data.out');}
  readln(k);
  for i:=1 to k do
    begin
      readln(e,n,c);
      factor(n);
      d:=1;
      while (1+k*(p-1)*(q-1)) mod e <> 0 do inc(k);
      d:=(1+k*(p-1)*(q-1)) div e;
      writeln(powmod(c,d,n));
    end;
end.

My program accept all my tests,but I have WA1. Can you give me some tests pls.

We can assume m=k*n+x. So
              m^e mod n = c
          <->(k*n+x)^e mod n = c
          <-> x^e mod n = c
=> We can find m in [1, n] : m^e mod n = c
=> My algorithm run in O(nlogn). Is it fast enough? (because it TLE on test#1)
Explain me!

My programm find secret key d (e*d mod (p-1)*(q-1)=1) and compute c^d mod n (=m) with "russian peasant method". But 0.981 sec is very bad.