ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1132. Квадратный корень

WA#2
Послано LNCP 8 фев 2015 09:50
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;
}
Re: WA#2
Послано LNCP 8 фев 2015 09:54
I had got AC now.Really a small mistake!