Submit Info #28103

Problem Lang User Status Time Memory
Kth Root(Mod) java dalt AC 269 ms 60.49 MiB

ケース詳細
Name Status Time Memory
Tonelli-Shanks_worstcase_00 AC 254 ms 51.68 MiB
Tonelli-Shanks_worstcase_01 AC 258 ms 59.89 MiB
Tonelli-Shanks_worstcase_02 AC 269 ms 60.49 MiB
Tonelli-Shanks_worstcase_03 AC 244 ms 56.79 MiB
Tonelli-Shanks_worstcase_04 AC 248 ms 48.94 MiB
example_00 AC 55 ms 9.48 MiB
max_random_00 AC 140 ms 14.98 MiB
max_random_01 AC 144 ms 15.00 MiB
max_random_02 AC 144 ms 15.02 MiB
max_random_03 AC 136 ms 13.97 MiB
max_random_04 AC 140 ms 14.83 MiB
random_00 AC 78 ms 9.89 MiB
random_01 AC 78 ms 9.98 MiB
random_02 AC 87 ms 10.10 MiB
random_03 AC 74 ms 9.88 MiB
random_04 AC 66 ms 9.48 MiB
safe_prime_00 AC 89 ms 10.36 MiB
safe_prime_01 AC 87 ms 10.32 MiB
safe_prime_02 AC 98 ms 10.54 MiB
safe_prime_03 AC 103 ms 10.52 MiB
safe_prime_04 AC 92 ms 10.44 MiB
small_00 AC 70 ms 9.96 MiB

import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.IOException; import java.util.HashMap; import java.io.UncheckedIOException; import java.io.Closeable; import java.io.Writer; import java.io.OutputStreamWriter; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top */ public class Main { public static void main(String[] args) throws Exception { Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29); thread.start(); thread.join(); } static class TaskAdapter implements Runnable { @Override public void run() { InputStream inputStream = System.in; OutputStream outputStream = System.out; FastInput in = new FastInput(inputStream); FastOutput out = new FastOutput(outputStream); KthRootMod solver = new KthRootMod(); int testCount = Integer.parseInt(in.next()); for (int i = 1; i <= testCount; i++) solver.solve(i, in, out); out.close(); } } static class KthRootMod { public void solve(int testNumber, FastInput in, FastOutput out) { int k = in.readInt(); int y = in.readInt(); int p = in.readInt(); KthRootModPrime modPrimeRoot = new KthRootModPrime(); long ans = modPrimeRoot.kth_root(y, k, p); assert ans == -1 || DigitUtils.modPow((int) ans, k, p) == y; out.println(ans); } } static class KthRootModPrime { public long kth_root(long a, long k, long p) { if (k == 0) return a == 1 ? 1 : -1; if (k > 0 && a == 0) return 0; long g = gcd(k, p - 1); if (pow(a, (p - 1) / g, p) != 1) return -1; a = pow(a, inv(k / g, (p - 1) / g), p); for (long div = 2; div * div <= g; ++div) { int sz = 0; while (g % div == 0) { g /= div; ++sz; } if (sz > 0) { long b = peth_root(a, div, sz, p); a = b; } } if (g > 1) a = peth_root(a, g, 1, p); return a; } private long peth_root(long a, long p, int e, long mod) { long q = mod - 1; int s = 0; while (q % p == 0) { q /= p; ++s; } long pe = pow(p, e, mod); long ans = pow(a, ((pe - 1) * inv(q, pe) % pe * q + 1) / pe, mod); long c = 2; while (pow(c, (mod - 1) / p, mod) == 1) ++c; c = pow(c, q, mod); HashMap<Long, Integer> map = new HashMap<>(); long add = 1; int v = (int) Math.sqrt(p) + 1; long mul = pow(c, v * pow(p, s - 1, mod - 1), mod); for (int i = 0; i <= v; ++i) { map.put(add, i); add = add * mul % mod; } mul = inv(pow(c, pow(p, s - 1, mod - 1), mod), mod); out: for (int i = e; i < s; ++i) { long err = inv(pow(ans, pe, mod), mod) * a % mod; long target = pow(err, pow(p, s - 1 - i, mod - 1), mod); for (int j = 0; j <= v; ++j) { if (map.containsKey(target % mod)) { int x = map.get(target % mod); ans = ans * pow(c, (j + v * x) * pow(p, i - e, mod - 1) % (mod - 1), mod) % mod; continue out; } target = target * mul % mod; } throw new AssertionError(); } return ans; } private long inv(long a, long p) { a %= p; long u = 1, v = 0; long b = p; while (b > 0) { long q = a / b; a %= b; u -= v * q % p; u %= p; { u ^= v; v ^= u; u ^= v; a ^= b; b ^= a; a ^= b; } } return u < 0 ? u + p : u; } private long pow(long a, long n, long p) { n %= p - 1; long r = 1; for (; n > 0; n >>= 1, a = a * a % p) if (n % 2 == 1) r = r * a % p; return r; } private long gcd(long a, long b) { return a == 0 ? b : gcd(b % a, a); } } static class FastInput { private final InputStream is; private StringBuilder defaultStringBuf = new StringBuilder(1 << 13); private byte[] buf = new byte[1 << 13]; private int bufLen; private int bufOffset; private int next; public FastInput(InputStream is) { this.is = is; } private int read() { while (bufLen == bufOffset) { bufOffset = 0; try { bufLen = is.read(buf); } catch (IOException e) { bufLen = -1; } if (bufLen == -1) { return -1; } } return buf[bufOffset++]; } public void skipBlank() { while (next >= 0 && next <= 32) { next = read(); } } public String next() { return readString(); } public int readInt() { int sign = 1; skipBlank(); if (next == '+' || next == '-') { sign = next == '+' ? 1 : -1; next = read(); } int val = 0; if (sign == 1) { while (next >= '0' && next <= '9') { val = val * 10 + next - '0'; next = read(); } } else { while (next >= '0' && next <= '9') { val = val * 10 - next + '0'; next = read(); } } return val; } public String readString(StringBuilder builder) { skipBlank(); while (next > 32) { builder.append((char) next); next = read(); } return builder.toString(); } public String readString() { defaultStringBuf.setLength(0); return readString(defaultStringBuf); } } static class FastOutput implements AutoCloseable, Closeable, Appendable { private static final int THRESHOLD = 1 << 13; private final Writer os; private StringBuilder cache = new StringBuilder(THRESHOLD * 2); public FastOutput append(CharSequence csq) { cache.append(csq); return this; } public FastOutput append(CharSequence csq, int start, int end) { cache.append(csq, start, end); return this; } private void afterWrite() { if (cache.length() < THRESHOLD) { return; } flush(); } public FastOutput(Writer os) { this.os = os; } public FastOutput(OutputStream os) { this(new OutputStreamWriter(os)); } public FastOutput append(char c) { cache.append(c); afterWrite(); return this; } public FastOutput append(long c) { cache.append(c); afterWrite(); return this; } public FastOutput append(String c) { cache.append(c); afterWrite(); return this; } public FastOutput println(long c) { return append(c).println(); } public FastOutput println() { return append(System.lineSeparator()); } public FastOutput flush() { try { os.append(cache); os.flush(); cache.setLength(0); } catch (IOException e) { throw new UncheckedIOException(e); } return this; } public void close() { flush(); try { os.close(); } catch (IOException e) { throw new UncheckedIOException(e); } } public String toString() { return cache.toString(); } } static class DigitUtils { private DigitUtils() { } public static int mod(long x, int mod) { if (x < -mod || x >= mod) { x %= mod; } if (x < 0) { x += mod; } return (int) x; } public static int mod(int x, int mod) { if (x < -mod || x >= mod) { x %= mod; } if (x < 0) { x += mod; } return x; } public static int modPow(int x, long n, int m) { if (n == 0) { return DigitUtils.mod(1, m); } int ans = modPow(x, n / 2, m); ans = DigitUtils.mod((long) ans * ans, m); if (n % 2 == 1) { ans = DigitUtils.mod((long) ans * x, m); } return ans; } } }