URAL 1132 2 번 남 았 습 니 다.

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define LL long long
struct Twice
{
    LL t1, t2;
    LL i, mod;
    Twice(){t1 = t2 = i = 0;}
    Twice(LL _t1, LL _t2, LL _t3, LL p){t1 = _t1, t2 = _t2, i = _t3, mod = p;}
    Twice operator * (Twice a)const{
        Twice ans;
        ans.t1 = (t1 * a.t1 % a.mod + t2 * a.t2 % a.mod * a.i) % a.mod;
        ans.t2 = (t1 * a.t2 % a.mod + t2 * a.t1 % a.mod) % a.mod;
        ans.i = i;
        ans.mod = mod;
        return ans;
    }
};
Twice power(Twice a, LL x, LL p)
{
    Twice ans = Twice(1, 0, a.i, p);
    while(x){
        if(x & 1)   ans = (ans * a);
        a = (a * a);
        x >>= 1;
    }
    return ans;
}
LL ppow(LL a, LL x, LL p)
{
    LL res = 1;
    while(x){
        if(x & 1)   res = (res * a) % p;
        a = (a * a) % p;
        x >>= 1;
    }
    return res;
}
LL Legendre(LL a, LL p)
{
    return ppow(a, (p - 1) >> 1, p);
}
LL solve(LL a, LL p)
{
    if(p == 2)  return 1;
    if(Legendre(a, p) + 1 == p)    return -1;
    LL t1, t2;
    for(LL i = 0 ; i < p ; i++){
        LL temp = i * i - a;
        temp = (temp % p + p) % p;
        if(Legendre(temp, p) + 1 == p){
            t1 = i, t2 = temp;
            break;
        }
    }
// printf("t1 = %I64d, t2 = %I64d
", t1, t2);
    Twice u = Twice(t1, 1, t2, p);
    u = power(u, (p + 1) / 2, p);
    return u.t1;
}
int main()
{
    int T;
    LL a, n;
    scanf("%d", &T);
    while(T--){
        cin >> a >> n;
        a %= n;
// scanf("%lld%lld", &a, &n);
        LL res = solve(a, n);
        if(n == 2){
            if(a == 1)  printf("1
");
            continue;
        }
        if(res == -1){
            printf("No root
");
            continue;
        }
// printf("res = %I64d
", res);
        LL b = n - res;
        if(res > b)   swap(res, b);
        if(res != b)  cout << res << " " << b << endl;
        else    cout << res << endl;
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <string> using namespace std;
#define LL long long LL n, p; LL a, w; struct Twice {
    LL a, b;
    Twice(){}
    Twice(LL _a, LL _b){a = _a, b = _b;}
    Twice operator * (Twice rbs)const{
        Twice ans;
        ans.a = (a * rbs.a + b * rbs.b * w) % p;
        ans.b = (b * rbs.a + a * rbs.b) % p;
        return ans;
    } }; LL ppow(LL a, LL x) {
    LL res = 1;
    while(x){
        if(x & 1)   res = (res * a) % p;
        a = (a * a) % p;
        x >>= 1;
    }
    return res; } Twice ppow(Twice a, LL x) {
    Twice res = Twice(1, 0);
    while(x){
        if(x & 1)   res = (res * a);
        a = (a * a);
        x >>= 1;
    }
    return res; } LL Legendre(LL a, LL x) {
    return ppow(a, (x - 1) / 2); } LL solve(LL n, LL p) {
    if(Legendre(n, p) + 1 == p)    return -1;
    for(a = 0 ; a < p ; a++){
        w = a * a - n;
        w = (w % p + p) % p;
        if(Legendre(w, p) + 1 == p) break;
    }
    Twice ans = ppow(Twice(a, 1), (p + 1) / 2);
    return ans.a; } int main() {
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%I64d%I64d", &n, &p); // printf("n = %I64d, p = %I64d
", n, p);
        if(p == 2){
            printf("1
");
            continue;
        }
        LL a = solve(n, p);
        if(a == -1){
            printf("No root
");
            continue;
        }
        LL b = p - a;
        if(a > b)   swap(a, b);
        printf("%I64d %I64d
", a, b);
    }
    return 0; }