Easy solution with O(p) and without using a primality of p. We can build a table of square roots modulo p and then...

0.046 - O(p) solution.
0.468 - O(p^2) solution, please add more tests.
UPD: understood, that there is cant be NO SOLUTION. But you can enlarge p.

Edited by author 10.08.2020 12:39

x^2 + y^2 = A * p + k;
you use this simple algorithm:
A = [0....p]
and simple Check:
first time : y = 0 and x = sqrt(A*p + k)
if(x*x == A*p + k) you should Print this answer: x and y
else
second time: x = (int) sqrt(A*p + k) and y = sqrt(A*p + k - (int)x*x)
if(x*x + y*y == A*p + k) you should Print this answer : x and y
else continue and increasing only ONE count of A

Sorry my English...

Edited by author 04.01.2014 13:44

Edited by author 26.05.2014 22:39

Does the checking system enter only prime number ('p')? Should I do a check of input data?

And

What is the distinction of test 8? I broke  my head, trying to solve the WA!

while (true) {
            int d = (int)Math.sqrt(kk);
            if (d*d==kk) {
                System.out.println(0+" "+d);
                return;
            } else {
                long d3 = kk-d*d;
                int dd = (int)Math.sqrt(d3);
                if (dd*dd==d3) {
                    System.out.println(dd+" "+d);
                    return;
                }
            }
            kk += p;
        }

I was crazy abt that prob. then submitted stupid brute force and got ac.why so? please somebody tell me how to get ac in
.015 sec with simple programming.

Upgrade of Timus test server happened on autumn 2008. I became several times faster, but very few time limits were changed. This problem is one that needs time limit to be lowered. Because with 1s TL and new servers some brute force solutions get AC - solutions that would never get AC on old testing server.

I suggest TL=0.2s considering that some languages (Java and C#) need about 0.1s to start program.

Well, i have problems with this problem)

When I send C++ solutions with such declaration: int d[100000] I receive Crash (access violation) at test 8 as it should be. But when I change it to int d[1000000] I receive Crash (stack overflow) at test 1.

Why? What is stack overflow? I use (or should I say don't use?) neither local variables nor recursion. Or maybe I just think so.

Memory limit here is 16 MB and size of int d[1000000] is 4 MB, right? Help me please!

UPD: I got AC by changing int d[1000000] to vector<int> d(1000000) but I still want to know answer to my question.

Edited by author 07.06.2009 14:57

In Russian, the name of the problem is noncomformizm, it should be nonco_n_formizm.

About 100 authors got WA, TL and Crash. If you still have AC with time 0.5 sec or more, try to find very simple and fast solution of this problem.

why this prog ac? i think u must add maxtest
#include <iostream>
#include <stdio.h>
#include <math.h>


using namespace std;


int main()
{
 int k,p,x,y;
 cin >> k >> p;
 for(int x=0; x<p; x++)for(int y=0; y<=x; y++)if((x*x+y*y)%p==k)
 {

   cout << x << " " << y;
   return 0;

 }
 return 0;
}

Number p is a prime number, 2 ≤ p ≤ 1000000; 0 ≤ k ≤ p−1.

p cannot be 1000000

part of my program:
...
for x:=0 to p-1 do
for y:=0 to p-1 do
if f(x,y,p)=(k mod p) then
begin
writeln(x,' ',y);
halt(0);
end;
writeln('NO SOLUTION');
end.
{-----------------------------------}
f(x,y,p) = ( x^2 + y^2 ) mod p

Give me this test plz
I think my alg is not incorrect

I get AC, but I can't undestand this...

var k,p,x,y:int64;
begin
k:=1;
p:=3;
x:=0;
y:=2;
// Like a test #0 (sample)
if (x*x+y*y)=k mod p then writeln('correct test') else writeln('uncorrect test');
// x^2+y^2=k(mod p)
end.

So, anybody can tell me, why sample test is "uncorrect"?

I wrote solution that uses enumeration and got WA#5. Then, I wrote bruteforce algo and got AC. And then i added checking to solution with enumeration, so it will generate Runtime Error instead of outputting NO SOLUTION or when resulting pair is incorrect. But it was still WA#5. 2Jury: maybe something wrong with checker? I hope you'll check it. Thanks.

For x:=0 to p-1 do
 For y:=0 to p-1 do
  Begin
 t1:=x*x; t2:=y*y;
If (t1+t2) mod p=k mod p then ...

Before, t1,t2:int64. There is no Overflow and no TLE.

Help, If you can.

Thanks a lot.

†