結果

問題 No.1287 えぬけー
コンテスト
ユーザー m_tsubasa
提出日時 2020-11-13 21:42:43
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 623 ms / 2,000 ms
コード長 2,878 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,151 ms
コンパイル使用メモリ 197,316 KB
最終ジャッジ日時 2025-01-15 22:43:05
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 5
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘long long int modrootsub(long long int, long long int, long long int, long long int)’:
main.cpp:83:19: warning: ‘pre’ may be used uninitialized [-Wmaybe-uninitialized]
   83 |     int n = subsub(g, pre, p, mod);
      |             ~~~~~~^~~~~~~~~~~~~~~~
main.cpp:77:18: note: ‘pre’ was declared here
   77 |     int t = err, pre, cnt = 0;
      |                  ^~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
// https://judge.yosupo.jp/submission/6863
#define ll long long

ll pom(ll a, ll n, int m) {
  ll x = 1;
  for (a %= m; n; n /= 2) n & 1 ? x = x * a % m : 0, a = a * a % m;
  return x;
}
ll gcd(ll p, ll q) {
  for (ll t; q;) t = p % q, p = q, q = t;
  return p;
}
ll exgcd(ll p, ll q, ll *x, ll *y) {
  ll tx, ty, t, x2 = 0, y2 = 1;
  *x = 1;
  *y = 0;
  while (q) {
    tx = *x - p / q * x2;
    *x = x2;
    x2 = tx;
    ty = *y - p / q * y2;
    *y = y2;
    y2 = ty;
    t = p % q;
    p = q;
    q = t;
  }
  return p;
}
ll inv(ll a, ll p) {
  ll x, y;
  ll d = exgcd(a, p, &x, &y);
  if (d != 1) return -1;
  return x > 0 ? x : x + p;
}

ll sq(ll n) {
  ll x = sqrt(n);
  for (; (x + 1) * (x + 1) <= n; x++)
    ;
  return x;
}
ll cb(ll n) {
  ll x = cbrt(n);
  for (; (x + 1) * (x + 1) * (x + 1) <= n; x++)
    ;
  return x;
}

int subsub(ll x, ll y, int p, int mod) {
  int cnt = 0;
  for (; y != 1; y = y * x % mod) cnt++;
  return cnt;
}

ll modrootsub(ll a, ll p, ll e, ll mod) {
  ll q = mod - 1;
  int s = 0;
  while (q % p == 0) q /= p, s++;

  ll pe = 1;
  for (int i = 0; i < e; i++) pe *= p;
  ll d = inv(pe - q % pe, pe) * q;

  ll ans = pom(a, (d + 1) / pe, mod);
  ll err = pom(a, d, mod);
  if (err == 1) return ans;
  int temp = 1;
  while (pom(++temp, (mod - 1) / p, mod) == 1)
    ;
  int z = pom(temp, q, mod);
  int g = pom(temp, (mod - 1) / p, mod);

  while (err != 1) {
    int t = err, pre, cnt = 0;
    while (t != 1) {
      pre = t;
      t = pom(t, p, mod);
      cnt++;
    }
    int n = subsub(g, pre, p, mod);
    t = pom(z, n, mod);
    for (int i = 0; i < s - cnt - e; i++) t = pom(t, p, mod);
    ans = ans * t % mod;
    for (int i = 0; i < e; i++) t = pom(t, p, mod);
    err = err * t % mod;
  }
  return ans;
}

ll modrootsub2(ll a, ll n, ll p) {
  ll p1 = p - 1, p2 = 1;
  for (ll temp; temp = gcd(p1, n), temp != 1;) p1 /= temp, p2 *= temp;
  ll d = inv(n % p1, p1);
  return pom(a, d, p);
}

ll modroot(ll a, ll n, ll p) {
  if (a == 0) return n ? 0 : -1;
  ll d = gcd(p - 1, n);
  if (pom(a, (p - 1) / d, p) != 1) return -1;
  a = pom(a, inv(n / d, (p - 1) / d), p);
  n = d;

  ll d1 = n, d2 = 1;
  for (ll temp; temp = gcd((p - 1) / n, d1), temp != 1;) d1 /= temp, d2 *= temp;

  a = modrootsub2(a, d1, p);

  for (ll i = 2; i * i * i * i <= p - 1; i++)
    if (d2 % i == 0) {
      d2 /= i;
      int e = 1;
      while (d2 % i == 0) d2 /= i, e++;
      a = modrootsub(a, i, e, p);
    }

  if (d2 != 1) {
    ll q2 = sq(d2);
    ll q3 = cb(d2);
    if (q2 * q2 == d2)
      a = modrootsub(a, q2, 2, p);
    else if (q3 * q3 * q3 == d2)
      a = modrootsub(a, q3, 3, p);
    else
      a = modrootsub(a, d2, 1, p);
  }

  return a;
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    int x, k;
    cin >> x >> k;
    cout << modroot(x, k, 1e9 + 7) << endl;
  }
  return 0;
}
0