#937404 (Java21) No.3030 ミラー・ラビン素数判定法のテスト

提出ソース
結果

問題	No.3030 ミラー・ラビン素数判定法のテスト
ユーザー	Yu_212
提出日時	2023-12-08 16:07:17
言語	Java21 (openjdk 21)
結果	AC
実行時間	2,078 ms / 9,973 ms
コード長	21,784 bytes
コンパイル時間	4,401 ms
コンパイル使用メモリ	97,332 KB
実行使用メモリ	55,756 KB
最終ジャッジ日時	2024-09-27 02:51:23
合計ジャッジ時間	12,305 ms
ジャッジサーバーID （参考情報）	judge1 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	69 ms 37,868 KB
testcase_01	AC	69 ms 38,016 KB
testcase_02	AC	71 ms 38,168 KB
testcase_03	AC	75 ms 38,096 KB
testcase_04	AC	1,595 ms 55,756 KB
testcase_05	AC	1,325 ms 53,392 KB
testcase_06	AC	672 ms 52,700 KB
testcase_07	AC	678 ms 52,640 KB
testcase_08	AC	569 ms 51,860 KB
testcase_09	AC	2,078 ms 54,352 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.StreamSupport;

import static java.lang.Math.*;

public class Main {
    static In in = new In();
    static Out out = new Out(false, false);
    static final long inf = 0x1fffffffffffffffL;
    static final int iinf = 0x3fffffff;
    static final double eps = 1e-9;
    static long mod = 998244353;


    void solve() {
        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            long x = in.nextLong();
            if (x < 1L << 62) {
                out.println(x, PrimeUtils.isPrime(x) ? 1 : 0);
            } else {
                out.println(x, BigInteger.valueOf(x).isProbablePrime(Integer.MAX_VALUE) ? 1 : 0);
            }
        }
    }

    public static void main(String... args) {
        new Main().solve();
        out.flush();
    }
}

class BigMontgomery {
    private final long n, r2, nInv;

    public BigMontgomery(long n) {
        long r2 = (1L << 62) % n;
        for (int i = 0; i < 66; i++) {
            r2 <<= 1;
            if (r2 >= n) {
                r2 -= n;
            }
        }
        long nInv = n;
        for (int i = 0; i < 5; ++i) {
            nInv *= 2 - n * nInv;
        }
        this.n = n;
        this.r2 = r2;
        this.nInv = nInv;
    }

    private static long high(long x, long y) {
        return multiplyHigh(x, y) + ((x >> 63) & y) + ((y >> 63) & x);
    }

    private long mr(long x) {
        return high(-nInv * x, n) + (x == 0 ? 0 : 1);
    }

    private long mr2(long x, long y) {
        return high(x, y) + high(-nInv * x * y, n) + (x * y == 0 ? 0 : 1);
    }

    public long mul(long x, long y) {
        long r = mr2(mr2(x, r2), y);
        return r < n ? r : r - n;
    }

    public long pow(long x, long y) {
        long z = mr2(x, r2);
        long r = 1;
        while (y > 0) {
            if ((y & 1) == 1) {
                r = mr2(r, z);
            }
            z = mr2(z, z);
            y >>= 1;
        }
        return r < n ? r : r - n;
    }
}

class PrimeUtils {
    private static final int[] bases = {15591, 2018, 166, 7429, 8064, 16045, 10503, 4399, 1949, 1295, 2776, 3620, 560, 3128, 5212, 2657, 2300, 2021, 4652, 1471, 9336, 4018, 2398, 20462, 10277, 8028, 2213, 6219, 620, 3763, 4852, 5012, 3185, 1333, 6227, 5298, 1074, 2391, 5113, 7061, 803, 1269, 3875, 422, 751, 580, 4729, 10239, 746, 2951, 556, 2206, 3778, 481, 1522, 3476, 481, 2487, 3266, 5633, 488, 3373, 6441, 3344, 17, 15105, 1490, 4154, 2036, 1882, 1813, 467, 3307, 14042, 6371, 658, 1005, 903, 737, 1887, 7447, 1888, 2848, 1784, 7559, 3400, 951, 13969, 4304, 177, 41, 19875, 3110, 13221, 8726, 571, 7043, 6943, 1199, 352, 6435, 165, 1169, 3315, 978, 233, 3003, 2562, 2994, 10587, 10030, 2377, 1902, 5354, 4447, 1555, 263, 27027, 2283, 305, 669, 1912, 601, 6186, 429, 1930, 14873, 1784, 1661, 524, 3577, 236, 2360, 6146, 2850, 55637, 1753, 4178, 8466, 222, 2579, 2743, 2031, 2226, 2276, 374, 2132, 813, 23788, 1610, 4422, 5159, 1725, 3597, 3366, 14336, 579, 165, 1375, 10018, 12616, 9816, 1371, 536, 1867, 10864, 857, 2206, 5788, 434, 8085, 17618, 727, 3639, 1595, 4944, 2129, 2029, 8195, 8344, 6232, 9183, 8126, 1870, 3296, 7455, 8947, 25017, 541, 19115, 368, 566, 5674, 411, 522, 1027, 8215, 2050, 6544, 10049, 614, 774, 2333, 3007, 35201, 4706, 1152, 1785, 1028, 1540, 3743, 493, 4474, 2521, 26845, 8354, 864, 18915, 5465, 2447, 42, 4511, 1660, 166, 1249, 6259, 2553, 304, 272, 7286, 73, 6554, 899, 2816, 5197, 13330, 7054, 2818, 3199, 811, 922, 350, 7514, 4452, 3449, 2663, 4708, 418, 1621, 1171, 3471, 88, 11345, 412, 1559, 194};
    private static final SieveOfEratosthenes sieve = new SieveOfEratosthenes();
    private static final int USE_SIEVE_LIMIT = 5000000;

    public static int getMinPrimeFactor(int n) {
        return sieve.minPrimeFactor(n);
    }

    public static int getNthPrime(int n) {
        return sieve.nthPrime(n);
    }

    public static boolean isPrime(int n) {
        if (n == 2 || n == 3 || n == 5 || n == 7) {
            return true;
        }
        if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) {
            return false;
        }
        if (n < 121) {
            return n > 1;
        }
        long h = n;
        h = ((h >> 16) ^ h) * 0x45D9F3B;
        h = ((h >> 16) ^ h) * 0x45D9F3B;
        h = ((h >> 16) ^ h) & 0xFF;
        int a = bases[(int)h];
        return millerRabin(n, a);
    }

    private static boolean millerRabin(long n, long a) {
        long d = n - 1;
        int s = 0;
        while ((d & 1) == 0) {
            s++;
            d >>= 1;
        }
        long x = pow(a, d, n);
        if (x == 1) {
            return true;
        }
        for (int r = 0; r < s; r++) {
            if (x == n - 1) {
                return true;
            }
            x = x * x % n;
        }
        return false;
    }

    public static long pow(long a, long b, long mod) {
        long x = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                x = x * a % mod;
            }
            a = a * a % mod;
            b >>= 1;
        }
        return x;
    }

    private static boolean millerRabinBm(long n, long a, BigMontgomery bm) {
        long d = n - 1;
        int s = 0;
        while ((d & 1) == 0) {
            s++;
            d >>= 1;
        }
        long x = bm.pow(a, d);
        if (x == 1) {
            return true;
        }
        for (int r = 0; r < s; r++) {
            if (x == n - 1) {
                return true;
            }
            x = bm.mul(x, x);
        }
        return false;
    }

    private static boolean millerRabinBi(long n, long a) {
        long d = n - 1;
        int s = 0;
        while ((d & 1) == 0) {
            s++;
            d >>= 1;
        }
        BigInteger bn = BigInteger.valueOf(n);
        BigInteger bn1 = bn.subtract(BigInteger.ONE);
        BigInteger x = BigInteger.valueOf(a).modPow(BigInteger.valueOf(d), bn);
        if (x.equals(BigInteger.ONE)) {
            return true;
        }
        for (int r = 0; r < s; r++) {
            if (x.equals(bn1)) {
                return true;
            }
            x = x.multiply(x).mod(bn);
        }
        return false;
    }

    public static boolean isPrime(long n) {
        if (n <= Integer.MAX_VALUE) {
            return isPrime((int)n);
        }
        if (n < 1L << 62) {
            BigMontgomery bm = new BigMontgomery(n);
            for (long a : new long[] {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
                if (!millerRabinBm(n, a, bm)) {
                    return false;
                }
            }
        } else {
            for (long a : new long[] {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
                if (!millerRabinBi(n, a)) {
                    return false;
                }
            }
        }
        return true;
    }

    public static List<Integer> getPrimesLessThan(int n) {
        List<Integer> primes = new ArrayList<>();
        for (int prime : sieve) {
            if (prime >= n) {
                break;
            }
            primes.add(prime);
        }
        return primes;
    }

    public static List<Integer> getNPrimes(int n) {
        List<Integer> primes = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            primes.add(sieve.nthPrime(i));
        }
        return primes;
    }

    public static Map<Integer, Integer> factorize(int n) {
        if (n <= USE_SIEVE_LIMIT) {
            return factorize0(n);
        } else {
            return factorize1(n);
        }
    }

    // O(N + Q * logN)
    private static Map<Integer, Integer> factorize0(int n) {
        Map<Integer, Integer> primeFactors = new LinkedHashMap<>();
        while (n > 1) {
            int primeFactor = getMinPrimeFactor(n);
            int count = 0;
            while (getMinPrimeFactor(n) == primeFactor) {
                count++;
                n /= primeFactor;
            }
            primeFactors.put(primeFactor, count);
        }
        return primeFactors;
    }

    // O(√N + Q * √N / logN)
    private static Map<Integer, Integer> factorize1(int n) {
        Map<Integer, Integer> primeFactors = new LinkedHashMap<>();
        int c = n;
        for (int prime : sieve) {
            int count = 0;
            while (c % prime == 0) {
                count++;
                c /= prime;
            }
            if (count > 0) {
                primeFactors.put(prime, count);
            }
            if (prime * prime >= n) {
                break;
            }
        }
        if (c > 1) {
            primeFactors.put(c, 1);
        }
        return primeFactors;
    }

    public static List<Integer> divisors(int n) {
        List<Integer> divisors = new ArrayList<>();
        divisors.add(1);
        Map<Integer, Integer> primeFactors = factorize(n);
        for (Map.Entry<Integer, Integer> entry : primeFactors.entrySet()) {
            int exp = entry.getValue();
            int s = divisors.size();
            for (int i = 0; i < s; i++) {
                int v = 1;
                for (int j = 0; j < exp; j++) {
                    v *= entry.getKey();
                    divisors.add(divisors.get(i) * v);
                }
            }
        }
        Collections.sort(divisors);
        return divisors;
    }
}

class SieveOfEratosthenes implements Iterable<Integer> {
    private final List<Integer> primes = new ArrayList<>();
    private int[] table;

    public SieveOfEratosthenes() {
        this(1000);
    }

    public SieveOfEratosthenes(int initialCapacity) {
        calcTable(initialCapacity);
    }

    private void calcTable(int n) {
        int oldCapacity = 0;
        int[] newTable = new int[n];
        if (table != null) {
            oldCapacity = table.length;
            System.arraycopy(table, 0, newTable, 0, oldCapacity);
        }
        table = newTable;
        for (int i = oldCapacity; i < n; i++) {
            table[i] = i;
        }
        for (int i = 2; i < n; i++) {
            if (i >= oldCapacity && table[i] == i) {
                primes.add(i);
            }
            for (int prime : primes) {
                if (prime > table[i] || (long)prime * i >= n) {
                    break;
                }
                table[prime * i] = prime;
            }
        }
    }

    private void grow(int minCapacity) {
        int oldCapacity = table.length;
        int newCapacity = (int)min(Integer.MAX_VALUE, max(minCapacity, (long)oldCapacity + (oldCapacity >> 1)));
        calcTable(newCapacity);
    }

    public int minPrimeFactor(int n) {
        if (table.length <= n) {
            grow(n + 1);
        }
        return table[n];
    }

    public int nthPrime(int n) {
        while (primes.size() <= n) {
            grow(table.length + 1);
        }
        return primes.get(n);
    }

    public int countLessThan(int n) {
        while (primes.get(primes.size() - 1) < n) {
            grow(table.length + 1);
        }
        int left = -1;
        int right = primes.size();
        while (right - left > 1) {
            int mid = (left + right) / 2;
            if (primes.get(mid) < n) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return right;
    }

    public Map<Integer, Integer> factorize(int n) {
        Map<Integer, Integer> primeFactors = new LinkedHashMap<>();
        while (n > 1) {
            int primeFactor = minPrimeFactor(n);
            int exp = 0;
            while (n % primeFactor == 0) {
                n /= primeFactor;
                exp++;
            }
            primeFactors.put(primeFactor, exp);
        }
        return primeFactors;
    }

    public long sumOfDivisors(int n) {
        long prod = 1;
        while (n > 1) {
            int primeFactor = minPrimeFactor(n);
            int factor = 1;
            long sum = 1;
            while (n % primeFactor == 0) {
                n /= primeFactor;
                factor *= primeFactor;
                sum += factor;
            }
            prod *= sum;
        }
        return prod;
    }

    public List<Integer> divisors(int n) {
        List<Integer> divisors = new ArrayList<>();
        divisors.add(1);
        Map<Integer, Integer> primeFactors = factorize(n);
        for (Map.Entry<Integer, Integer> entry : primeFactors.entrySet()) {
            int exp = entry.getValue();
            int s = divisors.size();
            for (int i = 0; i < s; i++) {
                int v = 1;
                for (int j = 0; j < exp; j++) {
                    v *= entry.getKey();
                    divisors.add(divisors.get(i) * v);
                }
            }
        }
        Collections.sort(divisors);
        return divisors;
    }

    public IntStream stream() {
        int characteristics = Spliterator.ORDERED | Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.NONNULL | Spliterator.IMMUTABLE;
        Spliterator.OfInt spliterator = Spliterators.spliteratorUnknownSize(iterator(), characteristics);
        return StreamSupport.intStream(spliterator, false);
    }

    @Override
    public PrimitiveIterator.OfInt iterator() {
        return new PrimitiveIterator.OfInt() {
            private int i = 0;

            @Override
            public int nextInt() {
                return nthPrime(i++);
            }

            @Override
            public boolean hasNext() {
                return true;
            }
        };
    }
}

class In {
    private final BufferedInputStream reader = new BufferedInputStream(System.in);
    private final byte[] buffer = new byte[0x10000];
    private int i = 0;
    private int length = 0;

    public int read() {
        if (i == length) {
            i = 0;
            try {
                length = reader.read(buffer);
            } catch (IOException ignored) {
            }
            if (length == -1) {
                return 0;
            }
        }
        if (length <= i) {
            throw new RuntimeException();
        }
        return buffer[i++];
    }

    public String next() {
        StringBuilder builder = new StringBuilder();
        int b = read();
        while (b < '!' || '~' < b) {
            b = read();
        }
        while ('!' <= b && b <= '~') {
            builder.appendCodePoint(b);
            b = read();
        }
        return builder.toString();
    }

    public String nextLine() {
        StringBuilder builder = new StringBuilder();
        int b = read();
        while (b != 0 && b != '\r' && b != '\n') {
            builder.appendCodePoint(b);
            b = read();
        }
        if (b == '\r') {
            read();
        }
        return builder.toString();
    }

    public int nextInt() {
        long val = nextLong();
        if (val < Integer.MIN_VALUE || Integer.MAX_VALUE < val) {
            throw new NumberFormatException();
        }
        return (int)val;
    }

    public long nextLong() {
        int b = read();
        while (b < '!' || '~' < b) {
            b = read();
        }
        boolean neg = false;
        if (b == '-') {
            neg = true;
            b = read();
        }
        long n = 0;
        int c = 0;
        while ('0' <= b && b <= '9') {
            n = n * 10 + b - '0';
            b = read();
            c++;
        }
        if (c == 0 || c >= 2 && n == 0) {
            throw new NumberFormatException();
        }
        return neg ? -n : n;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

    public char[] nextCharArray() {
        return next().toCharArray();
    }

    public String[] nextStringArray(int n) {
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = next();
        }
        return s;
    }

    public char[][] nextCharMatrix(int n, int m) {
        char[][] a = new char[n][m];
        for (int i = 0; i < n; i++) {
            a[i] = next().toCharArray();
        }
        return a;
    }

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        return a;
    }

    public int[] nextIntArray(int n, IntUnaryOperator op) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = op.applyAsInt(nextInt());
        }
        return a;
    }

    public int[][] nextIntMatrix(int h, int w) {
        int[][] a = new int[h][w];
        for (int i = 0; i < h; i++) {
            a[i] = nextIntArray(w);
        }
        return a;
    }

    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextLong();
        }
        return a;
    }

    public long[] nextLongArray(int n, LongUnaryOperator op) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = op.applyAsLong(nextLong());
        }
        return a;
    }

    public long[][] nextLongMatrix(int h, int w) {
        long[][] a = new long[h][w];
        for (int i = 0; i < h; i++) {
            a[i] = nextLongArray(w);
        }
        return a;
    }

    public List<List<Integer>> nextGraph(int n, int m, boolean directed) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            res.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int u = nextInt() - 1;
            int v = nextInt() - 1;
            res.get(u).add(v);
            if (!directed) {
                res.get(v).add(u);
            }
        }
        return res;
    }
}

class Out {
    private final PrintWriter out = new PrintWriter(System.out);
    private final PrintWriter err = new PrintWriter(System.err);
    public boolean autoFlush;
    public boolean enableDebug;

    public Out(boolean autoFlush, boolean enableDebug) {
        this.autoFlush = autoFlush;
        this.enableDebug = enableDebug;
    }

    public void debug(Object... args) {
        if (!enableDebug) {
            return;
        }
        if (args == null || args.getClass() != Object[].class) {
            args = new Object[] {args};
        }
        StackTraceElement stackTrace = Thread.currentThread().getStackTrace()[2];
        err.print(String.format("[%40s]  ", stackTrace.toString()));
        err.println(Arrays.stream(args).map(obj -> format(obj, true)).collect(Collectors.joining(" ")));
        err.flush();
    }

    private String format(Object obj, boolean canMultiline) {
        if (obj == null) return "null";
        Class<?> clazz = obj.getClass();
        if (clazz == Double.class) return String.format("%.10f", obj);
        if (clazz == int[].class) return Arrays.toString((int[])obj);
        if (clazz == long[].class) return Arrays.toString((long[])obj);
        if (clazz == char[].class) return String.valueOf((char[])obj);
        if (clazz == boolean[].class) return IntStream.range(0, ((boolean[])obj).length).mapToObj(i -> ((boolean[])obj)[i] ? "1" : "0").collect(Collectors.joining());
        if (clazz == double[].class) return Arrays.toString(Arrays.stream((double[])obj).mapToObj(a -> format(a, false)).toArray());
        if (canMultiline && clazz.isArray() && clazz.componentType().isArray()) return Arrays.stream((Object[])obj).map(a -> format(a, false)).collect(Collectors.joining("\n"));
        if (clazz == Object[].class) return Arrays.toString(Arrays.stream((Object[])obj).map(a -> format(a, false)).toArray());
        if (clazz.isArray()) return Arrays.toString((Object[])obj);
        return String.valueOf(obj);
    }

    public void println(Object... args) {
        if (args == null || args.getClass() != Object[].class) {
            args = new Object[] {args};
        }
        out.println(Arrays.stream(args)
                .map(obj -> obj instanceof Double ? String.format("%.10f", obj) : String.valueOf(obj))
                .collect(Collectors.joining(" ")));
        if (autoFlush) {
            out.flush();
        }
    }

    public void println(char a) {
        out.println(a);
        if (autoFlush) {
            out.flush();
        }
    }

    public void println(int a) {
        out.println(a);
        if (autoFlush) {
            out.flush();
        }
    }

    public void println(long a) {
        out.println(a);
        if (autoFlush) {
            out.flush();
        }
    }

    public void println(double a) {
        out.println(String.format("%.10f", a));
        if (autoFlush) {
            out.flush();
        }
    }

    public void println(String s) {
        out.println(s);
        if (autoFlush) {
            out.flush();
        }
    }

    public void println(char[] s) {
        out.println(String.valueOf(s));
        if (autoFlush) {
            out.flush();
        }
    }

    public void println(int[] a) {
        StringJoiner joiner = new StringJoiner(" ");
        for (int i : a) {
            joiner.add(Integer.toString(i));
        }
        out.println(joiner);
        if (autoFlush) {
            out.flush();
        }
    }

    public void println(long[] a) {
        StringJoiner joiner = new StringJoiner(" ");
        for (long i : a) {
            joiner.add(Long.toString(i));
        }
        out.println(joiner);
        if (autoFlush) {
            out.flush();
        }
    }

    public void flush() {
        err.flush();
        out.flush();
    }
}
yukicoder

結果

テストケース

ソースコード
