結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー mikit
提出日時 2018-11-29 14:42:03
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 6,104 bytes
コンパイル時間 3,835 ms
コンパイル使用メモリ 89,312 KB
実行使用メモリ 57,296 KB
最終ジャッジ日時 2024-11-18 16:31:08
合計ジャッジ時間 6,364 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.stream.IntStream;
import java.util.stream.LongStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        LightScanner in = new LightScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        No3030 solver = new No3030();
        solver.solve(1, in, out);
        out.close();
    }

    static class No3030 {
        public void solve(int testNumber, LightScanner in, PrintWriter out) {
            for (long x : in.longs(in.ints())) {
                out.println(x + " " + (IntMath.isPrime(x) ? 1 : 0));
            }
        }

    }

    static final class IntMath {
        private IntMath() {
        }

        public static boolean isPrime(int n) {
            if (n == 2) {
                return true;
            } else if (n <= 1 || (n & 1) == 0) {
                return false;
            }
            int s = BitMath.lsb(n - 1);
            int d = (n - 1) >> s;
            ModMath m = new ModMath(n);
            outer:
            for (int a : new int[]{2, 7, 61}) {
                int r = (int) m.pow(a, d);
                if (r == 1 || r == n - 1) {
                    continue;
                }
                for (int j = 0; j < s; j++) {
                    r = (int) m.pow(r, 2);
                    if (r == n - 1) {
                        continue outer;
                    }
                }
                return false;
            }
            return true;
        }

        public static boolean isPrime(long n) {
            if (n == 2) {
                return true;
            } else if (n <= 1 || (n & 1) == 0) {
                return false;
            } else if (n < Integer.MAX_VALUE) {
                return isPrime((int) n);
            }
            int s = BitMath.lsb(n - 1);
            long d = (n - 1) >> s;
            ModMath m = new ModMath(n);
            outer:
            for (int a : new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
                long r = m.pow(a, d);
                if (r == 1 || r == n - 1) {
                    continue;
                }
                for (int j = 0; j < s; j++) {
                    r = m.pow(r, 2);
                    if (r == n - 1) {
                        continue outer;
                    }
                }
                return false;
            }
            return true;
        }

    }

    static class LightScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;

        public LightScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public String string() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new UncheckedIOException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int ints() {
            return Integer.parseInt(string());
        }

        public long longs() {
            return Long.parseLong(string());
        }

        public long[] longs(int length) {
            return IntStream.range(0, length).mapToLong(x -> longs()).toArray();
        }

    }

    static class ModMath {
        private static final int DEFAULT_MOD = 1_000_000_007;
        private final long mod;

        public ModMath(long mod) {
            this.mod = mod;
        }

        public ModMath() {
            this(DEFAULT_MOD);
        }

        public long pow(long x, long y) {
            if (y == 0) {
                return 1;
            } else if (y % 2 == 0) {
                long z = pow(x, y / 2);
                return (z * z) % mod;
            } else {
                return (x % mod) * pow(x, y - 1) % mod;
            }
        }

    }

    static final class BitMath {
        private BitMath() {
        }

        public static int count(int v) {
            v = (v & 0x55555555) + ((v >> 1) & 0x55555555);
            v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
            v = (v & 0x0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f);
            v = (v & 0x00ff00ff) + ((v >> 8) & 0x00ff00ff);
            v = (v & 0x0000ffff) + ((v >> 16) & 0x0000ffff);
            return v;
        }

        public static int count(long v) {
            v = (v & 0x5555555555555555L) + ((v >> 1) & 0x5555555555555555L);
            v = (v & 0x3333333333333333L) + ((v >> 2) & 0x3333333333333333L);
            v = (v & 0x0f0f0f0f0f0f0f0fL) + ((v >> 4) & 0x0f0f0f0f0f0f0f0fL);
            v = (v & 0x00ff00ff00ff00ffL) + ((v >> 8) & 0x00ff00ff00ff00ffL);
            v = (v & 0x0000ffff0000ffffL) + ((v >> 16) & 0x0000ffff0000ffffL);
            v = (v & 0x00000000ffffffffL) + ((v >> 32) & 0x00000000ffffffffL);
            return (int) v;
        }

        public static int lsb(int v) {
            if (v == 0) {
                throw new IllegalArgumentException("Bit not found");
            }
            v |= (v << 1);
            v |= (v << 2);
            v |= (v << 4);
            v |= (v << 8);
            v |= (v << 16);
            return 32 - count(v);
        }

        public static int lsb(long v) {
            if (v == 0) {
                throw new IllegalArgumentException("Bit not found");
            }
            v |= (v << 1);
            v |= (v << 2);
            v |= (v << 4);
            v |= (v << 8);
            v |= (v << 16);
            v |= (v << 32);
            return 64 - count(v);
        }

    }
}
0