Publish worst case for your solution please. Is it when k=100000, n is always 8k+1, prime near 32767?

Don't understand... if for example, a=1, n=32 the result should be 1 15 17 31... not only 1 and 31

1. As I've understood, my old solution don't pass new tests only because there are pairs <a, n> : a >= n.

2. Brute force still gets AC in ~0.6 sec.

timus_support (at) acm.timus.ru

very nice :)

Can you explain me that better, I don't understand your idea.

YEAAAAAH, I got AC!!!

program Ural_1132;
var
  i,j,x,p,q,n:longint;

function power(a,b,c:longint):longint;
var
  d,s:longint;
begin
  d:=a;s:=1;
  while b>0 do
  begin
    if odd(b) then s:=(s*d) mod c;
    b:=b div 2;d:=(d*d) mod c;
  end;
  exit(s);
end;

begin
  read(n);
  for i:=1 to n do
  begin
    read(q,p);q:=q mod p;
    if (p=2) and (q=1) or (p<>2) and (power(q,(p-1) div 2,p)=p-1) then
    begin
      writeln('No root');
      continue;
    end;
    if trunc(sqrt(q))=0 then
    begin
      x:=trunc(sqrt(q));
      write(x);
      if p-x<>x then write(' ',p-x);
      writeln;
      continue;
    end;
    for j:=1 to (p-1) div 2 do
    begin
      x:=(j*j) mod p;
      if x=q then
      begin
        write(j);
        if p-j<>j then write(' ',p-j);
        writeln;
        break;
      end;
    end;
  end;
end.

Edited by author 07.03.2007 18:27

You had WA1 on this problem earlier. In what there was a mistake? Can at me same....
And please post some tests for this problem

>

>

>

I try to solve it with C++ too, Thank you very much I will translation it to
Pascal.
I hope I will got accepted.

I think that there is a simple formula that is going to
work....

I know the answer when (n mod 4)=3

The answer is +a^((n+1)/4), -a^((n+1)/4)

But I don't know the answer when (n mod 4)=1

I've read the pdf files, then write the program as the
algorithm described in the file, and also "Time Limit
Exceeded"!
What must I pay attention for?

The problem is really hard enough,
but the test data is really easy enough.
so the The solution is NOT really hard enough

 You know, I've realized algorithm "Zessenhaus-Kantor", but
it writes Time-limit!!! This algorithm has O(log n). What
is your algorithm?

Simple deterministic method with complexity O(sqrt(N)) is described in "The Art Of Computer Programming" (exercise 5.25). It's just enough - my program accepted in 0.890 sec.

The link is broken now...

url error??

Hi, I used the algorithm that is in the book you said, but I got TLE, can you help me?

if 19 appears, so 32 must do the same.
In this prob, we must understand to output all the X
satisfy the rule AND X <= N, that what i think about it :)

QH@

I have solution which take 1.001 sec for work...
It's - retrieval =)...
But - i can't make it faster... =(...

>

I wrote program that work 1.001 sec, but i can't make it
faster.
It's retrieval (searching)