I could solve it using trivial bruteforce. But I get TL, using more clever and probably expected solution. I used this: https://e-maxx.ru/algo/discrete_root (Read only first section, we don't need anything else). The slowest part here is Discrete Logarithm, which I calculate in \sqrt{n} * log_from_map.

We can qsort(n) and enumeration to solve it.
Notice that n is a prime.There are 2500 primes under 32767.
Enumeration can solve this problem.
And every ask have mostly 2 answers.最多2个解

I use Tonelli-Shanks algo,but i got WA#2.By now I had read all te topic but hadn't found the error.Please give me some hints or cases.
the key code:

int inverse(int a, int m)//thr inverse element of a(modulo m);
int quickpower(int a, int n, int m)//a^n(modulo m);
void sqrt(int a, int p)
{
    if(p==2)
    {
        cout << 1 << endl;
        return;
    }
    if(quickpower(a,(p-1)/2,p)!=1)
    {
        cout << "No root" << endl;
        return;
    }
    int s, t = 0, b = 0, i, j, x, y, inv, N;
    for (s = p - 1; !(s & 1); s /= 2) t++;
    inv = inverse(a, p);
    x = quickpower(a, (s + 1) / 2, p);
    for (N = 2; quickpower(N, (p - 1) / 2, p) == 1; N++);
    for (i = t - 2; i >= 0; i--)
    {
        b = b ? b*b%p : quickpower(N, s, p);
        y = x*x%p*inv%p;
        for (j = 1; j <= i; j++) y = y*y%p;
        if (y != 1) (x *= b) /= p;
    }
    if (2 * x < p) cout << x << " " << p - x << endl;
    else cout << p - x << " " << x << endl;
    return;
}

The problem states that the root should be in the range of (0, n - 1), which looks like saying 0 < x < n - 1. However apparently x can be equal to n - 1! I spent several hours stuck on WA 2 just because of this. Please change it to [0, n - 1] or whatever is precise.

i try so much ... in the beginning but i haven't got ACCEPTED ...



But now I have got accepted.
i use in the beginning a %= n.
after my program is accepted.

Edited by author 12.01.2014 15:15

i think there must be some stupid mistake.My all tests pass it. please provide me good tests or please,kindly let me know the problem in the code:

[code deleted]

AC at last(.187 sec 121 kb)

very very stupid mistake.
if(x==n-x) just print x not x and n-x :P

Edited by author 12.07.2010 10:41

Edited by author 13.07.2010 18:43

I keep getting WA2, even though I read all the topics and followed all your advices. I use Tonelli-Shanks algo, which seems to work fine on my test cases, but... If anyone had WA2 and managed to solve it, please tell me, might be something simillar. Thanks in advance :)

Edited by author 31.01.2012 21:26

The solution is really hard enough - you must know the
serious number theory :-) :-) :-)

read a book Handbook of applied cryptography
at http://cacr.math.uwaterloo.ca/hac/

Especcialy chapter 2 - mathematical background,
and the solution to the problem is written in chapter 3 -
subchapter about square root problem.

Author

First of all, K is large but the range of n is small (<=32767 and is prime);
So we can process the query with same n at the same time.

And use brute-force method;

Note if there are solutions there are exacly two solutions.

x and n-x ((n-x)^2=x^2(mod n));

According to this algo, we need to find b -- any quadratic non_residue modulo n, such 1<=b<=n-1. In my first programs I wrote

do
{
b=rand()%n;
}while(legendre(b, n)==1);

, so, in this case 0<=b<=n-1, and all they sometimes printed right answers, sometimes -- wrong, on identical tests. Be careful with it, I spent a lot of hours to find this very  stupid mistake. Right finding b is

do
{
b=1+rand()%(n-1);
}while(legendre(b, n)==1);

Edited by author 15.04.2011 22:18

Edited by author 15.04.2011 22:19

Edited by author 15.04.2011 22:19

Read the other topics carefully. Everything you need is said there.

Edited by author 01.05.2009 00:13

Hi,

For input 4 17, how come the output is 2 15 ? We have to do this right ?

sqrt(4 % 0) = undefined
sqrt(4 % 1) = 0
sqrt(4 % 2) = 0
sqrt(4 % 3) = 1
sqrt(4 % 4) = 0
sqrt(4 % 5) = 2
sqrt(4 % 6) = 2
sqrt(4 % 7) = 2
sqrt(4 % 8) = 2
sqrt(4 % 9) = 2
sqrt(4 % 10) = 2
..
..
sqrt(4 % 16) = 2

So where is 2 15 coming from ? Is there something wrong with the problem ?

Edited by author 20.04.2009 03:46

Edited by author 20.04.2009 03:46

After the rejudge my previously accepted solution got TL.
Today I logged in to the site, copy-pasted my old solution (from the site), submitted it and... surprisingly got AC!
Admins, don't you think it's strange?
And the time my program worked is 0.39 - far from TL...
Here are the ID's of my submits:
1526885 - TL
2460193 - AC

Ah! I think I will get an TLE but got AC the First Time!
You can use brute-force for n=8k+1 and use simple math method for other cases!

Edited by author 22.12.2008 20:46

Edited by author 22.12.2008 20:46

Old tests were rather weak so we have removed them and made new test set. Now the 1st test is a test from problem statement. All submits were rejudged, about 75% AC submits got WA and TL. Thanks to Vedernikoff Sergey for help.

some hints
if a == 1
output 1 n - 1;
in the begin a %= n;
this realy helps me with WA 2

Edited by author 26.08.2008 14:42

My definitely incorrect prog got AC! Where to send new tests?