結果
問題 | No.1232 2^x = x |
ユーザー | 遭難者 |
提出日時 | 2021-04-13 15:55:41 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 65 ms / 2,000 ms |
コード長 | 31,132 bytes |
コンパイル時間 | 3,433 ms |
コンパイル使用メモリ | 92,424 KB |
実行使用メモリ | 50,936 KB |
最終ジャッジ日時 | 2024-06-29 20:53:13 |
合計ジャッジ時間 | 4,652 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 47 ms
50,156 KB |
testcase_01 | AC | 53 ms
50,260 KB |
testcase_02 | AC | 64 ms
50,464 KB |
testcase_03 | AC | 65 ms
50,936 KB |
ソースコード
import java.util.*; import java.io.*; public class Main { public static void solve(ContestScanner sc, ContestPrinter ou) { int n = sc.nextInt(); for (int $ = 0; $ < n; $++) { long p = sc.nextInt(); ou.println(p == 2 ? 2 : mp(p - 1, p - 2, p) * (p - 1)); } } public static long mp(long a, long b, long m) { if (b == 0) return 1; if ((b & 1) == 1) return (a * mp(a, b - 1, m)) % m; return mp((a * a) % m, b >> 1, m); } public static void main(String[] args) { var sc = new ContestScanner(); var ou = new ContestPrinter(); solve(sc, ou); ou.flush(); ou.close(); } public static int intArray(int[] a, java.util.function.IntBinaryOperator map) { int s = a[0]; for (int i = 1; i < a.length; i++) s = map.applyAsInt(s, a[i]); return s; } public static long longArray(long[] a, java.util.function.LongBinaryOperator map) { long s = a[0]; for (int i = 1; i < a.length; i++) s = map.applyAsLong(s, a[i]); return s; } public static int max(int s, int... a) { for (int i : a) if (s < i) s = i; return s; } public static long max(long s, long... a) { for (long i : a) if (s < i) s = i; return s; } public static int min(int s, int... a) { for (int i : a) if (s > i) s = i; return s; } public static long min(long s, long... a) { for (long i : a) if (s > i) s = i; return s; } } class Point { int x; int y; Point(int x, int y) { this.x = x; this.y = y; } public int compareTo(Point p) { long c = this.x - p.x; if (c < 0) return -1; if (c > 0) return 1; return 0; } @Override public boolean equals(Object o) { if (o == this) return true; if (o.getClass() != this.getClass()) return false; Point p = (Point) o; return this.x == p.x && this.y == p.y; } @Override public int hashCode() { int result = x; result = 31 * result + y; return result; } } class Point2 { long x; int y; Point2(long x, int y) { this.x = x; this.y = y; } int compareTo(Point2 p) { long c = this.x - p.x; if (c < 0) return -1; if (c > 0) return 1; return 0; } @Override public boolean equals(Object o) { if (o == this) return true; if (o.getClass() != this.getClass()) return false; Point2 p = (Point2) o; return this.x == p.x && this.y == p.y; } @Override public int hashCode() { int result = (int) x; result = 31 * result + y; return result; } } class ModIntFactory { private final ModArithmetic ma; private final int mod; private final boolean usesMontgomery; private final ModArithmetic.ModArithmeticMontgomery maMontgomery; private ArrayList<Integer> factorial; public ModIntFactory(int mod) { this.ma = ModArithmetic.of(mod); this.usesMontgomery = ma instanceof ModArithmetic.ModArithmeticMontgomery; this.maMontgomery = usesMontgomery ? (ModArithmetic.ModArithmeticMontgomery) ma : null; this.mod = mod; this.factorial = new ArrayList<>(); } public ModInt create(long value) { if ((value %= mod) < 0) value += mod; if (usesMontgomery) { return new ModInt(maMontgomery.generate(value)); } else { return new ModInt((int) value); } } private void prepareFactorial(int max) { factorial.ensureCapacity(max + 1); if (factorial.size() == 0) factorial.add(1); for (int i = factorial.size(); i <= max; i++) { factorial.add(ma.mul(factorial.get(i - 1), i)); } } public ModInt factorial(int i) { prepareFactorial(i); return create(factorial.get(i)); } public ModInt permutation(int n, int r) { if (n < 0 || r < 0 || n < r) return create(0); prepareFactorial(n); return create(ma.div(factorial.get(n), factorial.get(r))); } public ModInt combination(int n, int r) { if (n < 0 || r < 0 || n < r) return create(0); prepareFactorial(n); return create(ma.div(factorial.get(n), ma.mul(factorial.get(r), factorial.get(n - r)))); } public int getMod() { return mod; } public class ModInt { private int value; private ModInt(int value) { this.value = value; } public int mod() { return mod; } public int value() { if (ma instanceof ModArithmetic.ModArithmeticMontgomery) { return ((ModArithmetic.ModArithmeticMontgomery) ma).reduce(value); } return value; } public ModInt add(ModInt mi) { return new ModInt(ma.add(value, mi.value)); } public ModInt add(ModInt mi1, ModInt mi2) { return new ModInt(ma.add(value, mi1.value)).addAsg(mi2); } public ModInt add(ModInt mi1, ModInt mi2, ModInt mi3) { return new ModInt(ma.add(value, mi1.value)).addAsg(mi2).addAsg(mi3); } public ModInt add(ModInt mi1, ModInt mi2, ModInt mi3, ModInt mi4) { return new ModInt(ma.add(value, mi1.value)).addAsg(mi2).addAsg(mi3).addAsg(mi4); } public ModInt add(ModInt mi1, ModInt... mis) { ModInt mi = add(mi1); for (ModInt m : mis) mi.addAsg(m); return mi; } public ModInt add(long mi) { return new ModInt(ma.add(value, ma.remainder(mi))); } public ModInt sub(ModInt mi) { return new ModInt(ma.sub(value, mi.value)); } public ModInt sub(long mi) { return new ModInt(ma.sub(value, ma.remainder(mi))); } public ModInt mul(ModInt mi) { return new ModInt(ma.mul(value, mi.value)); } public ModInt mul(ModInt mi1, ModInt mi2) { return new ModInt(ma.mul(value, mi1.value)).mulAsg(mi2); } public ModInt mul(ModInt mi1, ModInt mi2, ModInt mi3) { return new ModInt(ma.mul(value, mi1.value)).mulAsg(mi2).mulAsg(mi3); } public ModInt mul(ModInt mi1, ModInt mi2, ModInt mi3, ModInt mi4) { return new ModInt(ma.mul(value, mi1.value)).mulAsg(mi2).mulAsg(mi3).mulAsg(mi4); } public ModInt mul(ModInt mi1, ModInt... mis) { ModInt mi = mul(mi1); for (ModInt m : mis) mi.mulAsg(m); return mi; } public ModInt mul(long mi) { return new ModInt(ma.mul(value, ma.remainder(mi))); } public ModInt div(ModInt mi) { return new ModInt(ma.div(value, mi.value)); } public ModInt div(long mi) { return new ModInt(ma.div(value, ma.remainder(mi))); } public ModInt inv() { return new ModInt(ma.inv(value)); } public ModInt pow(long b) { return new ModInt(ma.pow(value, b)); } public ModInt addAsg(ModInt mi) { this.value = ma.add(value, mi.value); return this; } public ModInt addAsg(ModInt mi1, ModInt mi2) { return addAsg(mi1).addAsg(mi2); } public ModInt addAsg(ModInt mi1, ModInt mi2, ModInt mi3) { return addAsg(mi1).addAsg(mi2).addAsg(mi3); } public ModInt addAsg(ModInt mi1, ModInt mi2, ModInt mi3, ModInt mi4) { return addAsg(mi1).addAsg(mi2).addAsg(mi3).addAsg(mi4); } public ModInt addAsg(ModInt... mis) { for (ModInt m : mis) addAsg(m); return this; } public ModInt addAsg(long mi) { this.value = ma.add(value, ma.remainder(mi)); return this; } public ModInt subAsg(ModInt mi) { this.value = ma.sub(value, mi.value); return this; } public ModInt subAsg(long mi) { this.value = ma.sub(value, ma.remainder(mi)); return this; } public ModInt mulAsg(ModInt mi) { this.value = ma.mul(value, mi.value); return this; } public ModInt mulAsg(ModInt mi1, ModInt mi2) { return mulAsg(mi1).mulAsg(mi2); } public ModInt mulAsg(ModInt mi1, ModInt mi2, ModInt mi3) { return mulAsg(mi1).mulAsg(mi2).mulAsg(mi3); } public ModInt mulAsg(ModInt mi1, ModInt mi2, ModInt mi3, ModInt mi4) { return mulAsg(mi1).mulAsg(mi2).mulAsg(mi3).mulAsg(mi4); } public ModInt mulAsg(ModInt... mis) { for (ModInt m : mis) mulAsg(m); return this; } public ModInt mulAsg(long mi) { this.value = ma.mul(value, ma.remainder(mi)); return this; } public ModInt divAsg(ModInt mi) { this.value = ma.div(value, mi.value); return this; } public ModInt divAsg(long mi) { this.value = ma.div(value, ma.remainder(mi)); return this; } @Override public String toString() { return String.valueOf(value()); } @Override public boolean equals(Object o) { if (o instanceof ModInt) { ModInt mi = (ModInt) o; return mod() == mi.mod() && value() == mi.value(); } return false; } @Override public int hashCode() { return (1 * 37 + mod()) * 37 + value(); } } private static abstract class ModArithmetic { abstract int mod(); abstract int remainder(long value); abstract int add(int a, int b); abstract int sub(int a, int b); abstract int mul(int a, int b); int div(int a, int b) { return mul(a, inv(b)); } int inv(int a) { int b = mod(); if (b == 1) return 0; long u = 1, v = 0; while (b >= 1) { int t = a / b; a -= t * b; int tmp1 = a; a = b; b = tmp1; u -= t * v; long tmp2 = u; u = v; v = tmp2; } if (a != 1) throw new ArithmeticException("divide by zero"); return remainder(u); } int pow(int a, long b) { if (b < 0) throw new ArithmeticException("negative power"); int r = 1; int x = a; while (b > 0) { if ((b & 1) == 1) r = mul(r, x); x = mul(x, x); b >>= 1; } return r; } static ModArithmetic of(int mod) { if (mod <= 0) { throw new IllegalArgumentException(); } else if (mod == 1) { return new ModArithmetic1(); } else if (mod == 2) { return new ModArithmetic2(); } else if (mod == 998244353) { return new ModArithmetic998244353(); } else if (mod == 1000000007) { return new ModArithmetic1000000007(); } else if ((mod & 1) == 1) { return new ModArithmeticMontgomery(mod); } else { return new ModArithmeticBarrett(mod); } } private static final class ModArithmetic1 extends ModArithmetic { int mod() { return 1; } int remainder(long value) { return 0; } int add(int a, int b) { return 0; } int sub(int a, int b) { return 0; } int mul(int a, int b) { return 0; } int pow(int a, long b) { return 0; } } private static final class ModArithmetic2 extends ModArithmetic { int mod() { return 2; } int remainder(long value) { return (int) (value & 1); } int add(int a, int b) { return a ^ b; } int sub(int a, int b) { return a ^ b; } int mul(int a, int b) { return a & b; } } private static final class ModArithmetic998244353 extends ModArithmetic { private final int mod = 998244353; int mod() { return mod; } int remainder(long value) { return (int) ((value %= mod) < 0 ? value + mod : value); } int add(int a, int b) { int res = a + b; return res >= mod ? res - mod : res; } int sub(int a, int b) { int res = a - b; return res < 0 ? res + mod : res; } int mul(int a, int b) { return (int) (((long) a * b) % mod); } } private static final class ModArithmetic1000000007 extends ModArithmetic { private final int mod = 1000000007; int mod() { return mod; } int remainder(long value) { return (int) ((value %= mod) < 0 ? value + mod : value); } int add(int a, int b) { int res = a + b; return res >= mod ? res - mod : res; } int sub(int a, int b) { int res = a - b; return res < 0 ? res + mod : res; } int mul(int a, int b) { return (int) (((long) a * b) % mod); } } private static final class ModArithmeticMontgomery extends ModArithmeticDynamic { private final long negInv; private final long r2; private ModArithmeticMontgomery(int mod) { super(mod); long inv = 0; long s = 1, t = 0; for (int i = 0; i < 32; i++) { if ((t & 1) == 0) { t += mod; inv += s; } t >>= 1; s <<= 1; } long r = (1l << 32) % mod; this.negInv = inv; this.r2 = (r * r) % mod; } private int generate(long x) { return reduce(x * r2); } private int reduce(long x) { x = (x + ((x * negInv) & 0xffff_ffffl) * mod) >>> 32; return (int) (x < mod ? x : x - mod); } @Override int remainder(long value) { return generate((value %= mod) < 0 ? value + mod : value); } @Override int mul(int a, int b) { return reduce((long) a * b); } @Override int inv(int a) { return super.inv(reduce(a)); } @Override int pow(int a, long b) { return generate(super.pow(a, b)); } } private static final class ModArithmeticBarrett extends ModArithmeticDynamic { private static final long mask = 0xffff_ffffl; private final long mh; private final long ml; private ModArithmeticBarrett(int mod) { super(mod); long a = (1l << 32) / mod; long b = (1l << 32) % mod; long m = a * a * mod + 2 * a * b + (b * b) / mod; mh = m >>> 32; ml = m & mask; } private int reduce(long x) { long z = (x & mask) * ml; z = (x & mask) * mh + (x >>> 32) * ml + (z >>> 32); z = (x >>> 32) * mh + (z >>> 32); x -= z * mod; return (int) (x < mod ? x : x - mod); } @Override int remainder(long value) { return (int) ((value %= mod) < 0 ? value + mod : value); } @Override int mul(int a, int b) { return reduce((long) a * b); } } private static class ModArithmeticDynamic extends ModArithmetic { final int mod; ModArithmeticDynamic(int mod) { this.mod = mod; } int mod() { return mod; } int remainder(long value) { return (int) ((value %= mod) < 0 ? value + mod : value); } int add(int a, int b) { int sum = a + b; return sum >= mod ? sum - mod : sum; } int sub(int a, int b) { int sum = a - b; return sum < 0 ? sum + mod : sum; } int mul(int a, int b) { return (int) (((long) a * b) % mod); } } } } class ContestScanner { private final InputStream in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; public ContestScanner(InputStream in) { this.in = in; } public ContestScanner() { this(System.in); } private boolean hasNextByte() { if (ptr < buflen) return true; ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) return false; return true; } private int readByte() { return hasNextByte() ? buffer[ptr++] : -1; } private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } public boolean hasNext() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public void nextThrow(int n) { for (int i = 0; i < n; i++) this.next(); } public void nextThrow() { this.nextThrow(1); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) throw new NumberFormatException(); while (true) { if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; } else if (b == -1 || !isPrintableChar(b)) return minus ? -n : n; else throw new NumberFormatException(); b = readByte(); } } public int nextInt() { long nl = nextLong(); if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException(); return (int) nl; } public double nextDouble() { return Double.parseDouble(next()); } public boolean[] nextBoolean(char True) { String s = this.next(); int n = s.length(); boolean[] array = new boolean[n]; for (int i = 0; i < n; i++) array[i] = s.charAt(i) == True; return array; } public long[] nextLongArray(int length) { long[] array = new long[length]; for (int i = 0; i < length; i++) array[i] = this.nextLong(); return array; } public long[] nextLongArray(int length, java.util.function.LongUnaryOperator map) { long[] array = new long[length]; for (int i = 0; i < length; i++) array[i] = map.applyAsLong(this.nextLong()); return array; } public int[] nextIntArray(int length) { int[] array = new int[length]; for (int i = 0; i < length; i++) array[i] = this.nextInt(); return array; } public int[] nextIntArray(int length, java.util.function.IntUnaryOperator map) { int[] array = new int[length]; for (int i = 0; i < length; i++) array[i] = map.applyAsInt(this.nextInt()); return array; } public int[] nextIntArray(int length, int[] array) { int n = length + array.length; int[] a = new int[n]; for (int i = 0; i < length; i++) a[i] = this.nextInt(); for (int i = length; i < n; i++) a[i] = array[i - length]; return a; } public Integer[] nextIntegerArray(int length, java.util.function.IntUnaryOperator map) { Integer[] array = new Integer[length]; for (int i = 0; i < length; i++) array[i] = map.applyAsInt(this.nextInt()); return array; } public Integer[] nextIntegerArray(int length) { Integer[] array = new Integer[length]; for (int i = 0; i < length; i++) array[i] = this.nextInt(); return array; } public double[] nextDoubleArray(int length) { double[] array = new double[length]; for (int i = 0; i < length; i++) array[i] = this.nextDouble(); return array; } public double[] nextDoubleArray(int length, java.util.function.DoubleUnaryOperator map) { double[] array = new double[length]; for (int i = 0; i < length; i++) array[i] = map.applyAsDouble(this.nextDouble()); return array; } public String[] nextArray(int length) { String[] array = new String[length]; for (int i = 0; i < length; i++) array[i] = this.next(); return array; } public long[][] nextLongMatrix(int height, int width) { long[][] mat = new long[height][width]; for (int h = 0; h < height; h++) for (int w = 0; w < width; w++) mat[h][w] = this.nextLong(); return mat; } public int[][] nextIntMatrix(int height, int width) { int[][] mat = new int[height][width]; for (int h = 0; h < height; h++) for (int w = 0; w < width; w++) mat[h][w] = this.nextInt(); return mat; } public int[][] nextIntMatrix(int height, int width, java.util.function.IntUnaryOperator map) { int[][] mat = new int[height][width]; for (int h = 0; h < height; h++) for (int w = 0; w < width; w++) mat[h][w] = map.applyAsInt(this.nextInt()); return mat; } public double[][] nextDoubleMatrix(int height, int width) { double[][] mat = new double[height][width]; for (int h = 0; h < height; h++) for (int w = 0; w < width; w++) mat[h][w] = this.nextDouble(); return mat; } public boolean[][] nextBooleanMatrix(int height, int width, char True) { boolean[][] mat = new boolean[height][width]; for (int h = 0; h < height; h++) { String s = this.next(); for (int w = 0; w < width; w++) mat[h][w] = s.charAt(w) == True; } return mat; } public char[][] nextCharMatrix(int height, int width) { char[][] mat = new char[height][width]; for (int h = 0; h < height; h++) { String s = this.next(); for (int w = 0; w < width; w++) mat[h][w] = s.charAt(w); } return mat; } public char[][] nextCharMatrix(int height, int width, int h, int w, char c) { char[][] mat = new char[height + 2 * h][width + 2 * w]; for (int i = 0; i < height; i++) { String s = this.next(); for (int j = 0; j < width; j++) mat[i + h][j + w] = s.charAt(j); } for (int i = 0; i < h; i++) for (int j = 0; j < 2 * w + width; j++) mat[i][j] = c; for (int i = h + height; i < 2 * h + height; i++) for (int j = 0; j < 2 * w + width; j++) mat[i][j] = c; for (int i = h; i < h + height; i++) { for (int j = 0; j < w; j++) mat[i][j] = c; for (int j = w + width; j < 2 * w + width; j++) mat[i][j] = c; } return mat; } public boolean[][] nextBooleanMatrix(int height, int width, int h, int w, char c) { boolean[][] mat = new boolean[height + 2 * h][width + 2 * w]; for (int i = 0; i < height; i++) { String s = this.next(); for (int j = 0; j < width; j++) mat[i + h][j + w] = s.charAt(j) == c; } return mat; } } class ContestPrinter extends PrintWriter { public ContestPrinter(PrintStream stream) { super(stream); } public ContestPrinter() { super(System.out); } private static String dtos(double x, int n) { StringBuilder sb = new StringBuilder(); if (x < 0) { sb.append('-'); x = -x; } x += Math.pow(10, -n) / 2; sb.append((long) x); sb.append("."); x -= (long) x; for (int i = 0; i < n; i++) { x *= 10; sb.append((int) x); x -= (int) x; } return sb.toString(); } @Override public void print(float f) { super.print(dtos(f, 20)); } @Override public void println(float f) { super.println(dtos(f, 20)); } @Override public void print(double d) { super.print(dtos(d, 20)); } @Override public void println(double d) { super.println(dtos(d, 20)); } public void printlnArray(String[] array) { for (String i : array) super.println(i); } public void printArray(int[] array, String separator) { int n = array.length - 1; for (int i = 0; i < n; i++) { super.print(array[i]); super.print(separator); } super.println(array[n]); } public void printArray(int[] array) { this.printArray(array, " "); } public void printArray(Integer[] array) { this.printArray(array, " "); } public void printArray(Integer[] array, String separator) { int n = array.length - 1; for (int i = 0; i < n; i++) { super.print(array[i]); super.print(separator); } super.println(array[n]); } public void printlnArray(int[] array) { for (int i : array) super.println(i); } public void printArray(int[] array, String separator, java.util.function.IntUnaryOperator map) { int n = array.length - 1; for (int i = 0; i < n; i++) { super.print(map.applyAsInt(array[i])); super.print(separator); } super.println(map.applyAsInt(array[n])); } public void printlnArray(int[] array, java.util.function.IntUnaryOperator map) { for (int i : array) super.println(map.applyAsInt(i)); } public void printlnArray(long[] array, java.util.function.LongUnaryOperator map) { for (long i : array) super.println(map.applyAsLong(i)); } public void printArray(int[] array, java.util.function.IntUnaryOperator map) { this.printArray(array, " ", map); } public void printArray(long[] array, String separator) { int n = array.length - 1; for (int i = 0; i < n; i++) { super.print(array[i]); super.print(separator); } super.println(array[n]); } public void printArray(long[] array) { this.printArray(array, " "); } public void printlnArray(long[] array) { for (long i : array) super.println(i); } public void printArray(boolean[] array, String a, String b) { int n = array.length - 1; for (int i = 0; i < n; i++) super.print((array[i] ? a : b) + " "); super.println(array[n] ? a : b); } public void printArray(boolean[] array) { this.printArray(array, "Y", "N"); } public void printArray(long[] array, String separator, java.util.function.LongUnaryOperator map) { int n = array.length - 1; for (int i = 0; i < n; i++) { super.print(map.applyAsLong(array[i])); super.print(separator); } super.println(map.applyAsLong(array[n])); } public void printArray(long[] array, java.util.function.LongUnaryOperator map) { this.printArray(array, " ", map); } public void printArray(ArrayList<?> array) { this.printArray(array, " "); } public void printArray(ArrayList<?> array, String separator) { int n = array.size() - 1; for (int i = 0; i < n; i++) { super.print(array.get(i).toString()); super.print(separator); } super.println(array.get(n).toString()); } public void printlnArray(ArrayList<?> array) { int n = array.size(); for (int i = 0; i < n; i++) super.println(array.get(i).toString()); } public void printArray(int[][] array) { int n = array.length; if (n == 0) return; int m = array[0].length - 1; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) super.print(array[i][j] + " "); super.println(array[i][m]); } } public void printArray(long[][] array) { int n = array.length; if (n == 0) return; int m = array[0].length - 1; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) super.print(array[i][j] + " "); super.println(array[i][m]); } } }