結果

問題 No.1287 えぬけー
コンテスト
ユーザー 0w1
提出日時 2020-11-13 22:57:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,090 bytes
コンパイル時間 3,914 ms
コンパイル使用メモリ 214,544 KB
最終ジャッジ日時 2025-01-15 23:51:16
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other WA * 1 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const int p = 1e9 + 7;
const int g = 5;
struct PrimeFactor {
  static long long mul(long long x, long long y, long long mod) {
    long long m = x, s = 0;
    for (; y; y >>= 1, m <<= 1, m = m >= mod ? m - mod : m)
      if (y & 1) s += m, s = s >= mod ? s - mod : s;
    return s;
  }
  static long long powmod(long long x, long long p, long long mod) {
    long long s = 1, m = x % mod;
    for (; p; m = mul(m, m, mod), p >>= 1)
      if (p & 1) s = mul(s, m, mod);
    return s;
  }
  static bool miller_rabin(long long n, int s = 7) {
    static const long long wits[7] = {
      2, 325, 9375, 28178, 450775, 9780504, 1795265022
    };
    auto witness = [&](long long a, long long n, long long u, int t) {
      long long x = powmod(a, u, n), nx;
      for (int i = 0; i < t; ++i, x = nx) {
        nx = mul(x, x, n);
        if (nx == 1 && x != 1 && x != n - 1) return true;
      }
      return x != 1;
    };
    if (n < 2) return 0;
    if (~n & 1) return n == 2;
    long long u = n - 1, t = 0, a;
    for (; ~u & 1; u >>= 1) ++t;
    while (s--) if ((a = wits[s] % n) && witness(a, n, u, t)) return false;
    return true;
  }
  static long long pollard_rho(long long n) {
    auto f = [](long long x, long long n) { return mul(x, x, n) + 1; };
    if (~n & 1) return 2;
    while (true) {
      long long x = rand() % (n - 1) + 1, y = 2, d = 1;
      for (int sz = 2; d == 1; y = x, sz <<= 1)
        for (int i = 0; i < sz && d <= 1; ++i)
          x = f(x, n), d = __gcd(abs(x - y), n);
      if (d && n - d) return d;
    }
  }
  static vector<pair<long long, int>> factorize(long long n) {
    set<long long> factors;
    function<void(long long)> rec = [&](long long x) {
      if (x == 1) return;
      if (miller_rabin(x)) return void(factors.emplace(x));
      auto u = pollard_rho(x);
      rec(u);
      for (auto p : factors) while (x % p == 0) x /= p;
      rec(x);
    };
    rec(n);
    vector<pair<long long, int>> res;
    for (auto p : factors) {
      res.emplace_back(p, 0);
      for (; n % p == 0; n /= p) ++res.back().second;
    }
    return res;
  }
};
tuple<int, int, int> ext_gcd(int a, int b) {
  if (!b) return {1, 0, a};
  int x, y, g;
  tie(x, y, g) = ext_gcd(b, a % b);
  return {y, x - a / b * y, g};
}
const int magic = 1000;
map<int, int> mp;
int x;
int discrete_log(int a, int m) { // a**x = m mod p
  for (int i = 0, y = 1; i <= magic; ++i) {
    int inv = get<0>(ext_gcd(y, p));
    if (inv < 0) inv += p;
    int u = 1LL * m * inv % p;
    if (mp.count(u)) return i * (p / magic) + mp[u];
    y = 1LL * y * x % p;
  }
  return -1;
}
int generator() { // modulo prime p, O(x*log(phi(p))*log(p)), x = O(lg^6p)
  auto fp = PrimeFactor::factorize(p);
  int phi = p;
  for (auto u : fp) phi = phi / u.first * (u.first - 1);
  auto pp = PrimeFactor::factorize(phi);
  auto int_pow = [](int v, int n, int p) {
    int r = 1;
    for (int i = n; i; i >>= 1) {
      if (i & 1) r = 1LL * r * v % p;
      v = 1LL * v * v % p;
    }
    return r;
  };
  auto check = [&](int g) {
    for (auto u : pp) {
      int t = int_pow(g, phi / u.first, p);
      if (t == 1) return false;
    }
    return true;
  };
  for (int i = 2; ; ++i) {
    if (check(i)) return i;
  }
  return -1;
}
int discrete_kth_root(int n, int m) { // x**n = m mod p
  int q = discrete_log(g, m);
  if (q == -1) return -1;

  int x, y, d;
  tie(x, y, d) = ext_gcd(n, p - 1);
  if (q % d) return -1; // conclusion of no solution by ext_gcd

  int w = x;
  if (w < 0) w = w % ((p - 1) / d) + (p - 1) / d; // normalize to non-negative

  int r = 1; // g**q = g**(n*w') = (g**w')**n -> x = g**w'
  int ng = g;
  for (int64_t i = 1LL * q / d * w; i; i >>= 1) {
    if (i & 1) r = 1LL * r * ng % p;
    ng = 1LL * ng * ng % p;
  }
  return r;
}

int main() {
  ios::sync_with_stdio(false);

  int T; { cin >> T; }

  {
    x = 1;
    for (int i = 0; i < p / magic; ++i) {
      mp[x] = i;
      x = 1LL * x * g % p;
    }
  }

  while (T--) {
    int X, K; {
      cin >> X >> K;
    }
    cout << discrete_kth_root(K, X) << "\n";
  }
}
0