模意义下开根的Tonelli-Shanks算法

讲解

Timus上的例题

代码如下。(超懒不想写解说)

#include "bits/stdc++.h"
using namespace std;

using ux = long long;
ux modpow(ux a, ux b, ux p)
{
  ux c = 1;
  while (b) {
    if (b & 1) (c *= a) %= p;
    (a *= a) %= p;
    b >>= 1;
  }
  return c;
}
bool Euler_criterion(ux n, ux p)
{
  return modpow(n, p / 2, p) == 1;
}
ux TonelliShanks(ux n, ux p)
{
  if (!Euler_criterion(n, p)) return 0;
  ux Q = p - 1;
  ux S = 0;
  while (~Q & 1) Q >>= 1, S++;
  ux z = 2;
  while (Euler_criterion(z, p)) ++z;
  ux M = S,
    c = modpow(z, Q, p),
    t = modpow(n, Q, p),
    R = modpow(n, (Q + 1) / 2, p);
  while (t > 1) {
    if (t == 0) return 0;
    ux f = t;
    ux i = 0;
    while (f != 1) {
      (f *= f) %= p;
      ++i;
    }
    ux b = c;
    for (int j = 0; j < M - i - 1; ++j) {
      (b *= b) %= p;
    }
    M = i;
    c = b * b % p;
    t = t * c % p;
    R = R * b % p;
  }
  return R;
}

int main()
{
  cin.sync_with_stdio(false); cin.tie(0);
  int T; cin >> T;
  while (T--) {
    ux x, p;
    cin >> x >> p;
    if (p == 2) {
      cout << 1 << '\n';
    } else if (Euler_criterion(x, p)) {
      ux r = TonelliShanks(x, p);
      r = min(r, p - r);
      cout << r << ' ' << p - r << '\n';
    } else {
      cout << "No root\n";
    }
  }
  return 0;
}