Submit Info #23496

Problem Lang User Status Time Memory
Kth Root(Mod) cpp (anonymous) AC 4093 ms 13.05 MiB

ケース詳細
Name Status Time Memory
Tonelli-Shanks_worstcase_00 AC 2150 ms 13.05 MiB
Tonelli-Shanks_worstcase_01 AC 2337 ms 13.05 MiB
Tonelli-Shanks_worstcase_02 AC 2263 ms 13.04 MiB
Tonelli-Shanks_worstcase_03 AC 2339 ms 13.00 MiB
Tonelli-Shanks_worstcase_04 AC 2142 ms 13.05 MiB
example_00 AC 5 ms 8.99 MiB
max_random_00 AC 3441 ms 12.95 MiB
max_random_01 AC 3296 ms 13.00 MiB
max_random_02 AC 3346 ms 13.02 MiB
max_random_03 AC 3545 ms 13.00 MiB
max_random_04 AC 3404 ms 13.05 MiB
random_00 AC 270 ms 12.92 MiB
random_01 AC 759 ms 13.00 MiB
random_02 AC 1660 ms 12.92 MiB
random_03 AC 437 ms 12.94 MiB
random_04 AC 317 ms 12.91 MiB
safe_prime_00 AC 4014 ms 12.92 MiB
safe_prime_01 AC 4050 ms 12.92 MiB
safe_prime_02 AC 3924 ms 13.02 MiB
safe_prime_03 AC 4067 ms 12.94 MiB
safe_prime_04 AC 4093 ms 12.92 MiB
small_00 AC 8 ms 9.05 MiB

#pragma GCC optimization ("unroll-loops") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4") #include <bits/stdc++.h> using namespace std; namespace TaggedHashSet { const int MaxL = 1 << 20; int timer[MaxL], who[MaxL], store[MaxL], dat; int hasher(int idx) { idx ^= 6236843899; idx = 180161 * idx + 106192; return idx & (MaxL - 1); } void Init() { memset(timer, -1, sizeof(timer)); memset(who, -1, sizeof(who)); dat = 0; } void Clear() { ++dat; } int Count(int key) { int idx = hasher(key); int bar = 0; while (timer[idx] == dat && key != who[idx]) { idx = (idx + 1) & (MaxL - 1); } return timer[idx] == dat && key == who[idx] ? store[idx] : -1; } void Insert(int key, int val) { int idx = hasher(key); int bar = 0; while (timer[idx] == dat && key != who[idx]) { idx = (idx + 1) & (MaxL - 1); } timer[idx] = dat; who[idx] = key; store[idx] = val; } }; int main() { // freopen("input.txt", "r", stdin); const int N = 1 << 16; vector <int> lp(N, 0), pr; for (int i = 2; i < N; ++i) { if (!lp[i]) { lp[i] = i; pr.push_back(i); } for (int j = 0; j < (int)pr.size() && i * pr[j] < N && pr[j] <= lp[i]; ++j) { lp[i * pr[j]] = pr[j]; } } int t; scanf("%d", &t); TaggedHashSet::Init(); srand(time(0)); while (t--) { int k, y, p; scanf("%d%d%d", &k, &y, &p); if (k > 0) { k %= p - 1; if (!k) { k = p - 1; } } if (k == 0) { if (y == 1) { printf("0\n"); } else { printf("-1\n"); } continue; } if (y == 0) { printf("0\n"); continue; } auto Pow = [&](int a, int n, int mod) { int r = 1; while (n > 0) { if (n & 1) { r = 1LL * r * a % mod; } a = 1LL * a * a % mod; n >>= 1; } return r; }; auto findGen = [&](int md) { int _phi = md - 1; //phi(md) int val = _phi; vector <int> divisorsPhi; for (int i = 0; i < (int)pr.size() && pr[i] * pr[i] <= val; ++i) { if (val % pr[i] == 0) { divisorsPhi.push_back(pr[i]); } while (val % pr[i] == 0) { val /= pr[i]; } } if (val > 1) { divisorsPhi.push_back(val); } int g = 1; while (g < md) { bool ok = true; for (auto it : divisorsPhi) { ok &= Pow(g, _phi / it, md) != 1; } if (ok) { break; } ++g; } assert (g < md); return g >= md ? -1 : g; }; //(G^K)^X = Y (mod P) //(G^X)^K = Y (mod P) int G = findGen(p); int Gk = Pow(G, k, p); int S = (int)sqrtl(p * 1.0); for (int i = 0, cur = 1; i < S; ++i, cur = 1LL * cur * Gk % p) { TaggedHashSet::Insert(cur, i); } int iGk = Pow(Pow(Gk, S, p), p - 2, p); int ans = -1; for (int i = 0, cur = y; i < p - 1 && !~ans; i += S, cur = 1LL * cur * iGk % p) { int foo = TaggedHashSet::Count(cur); if (~foo) { ans = i + foo; } } TaggedHashSet::Clear(); if (~ans) { ans = Pow(G, ans, p); } printf("%d\n", ans); } return 0; }