結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー yuppe19 😺
提出日時 2017-10-30 14:52:07
言語 Java
(openjdk 23)
結果
AC  
実行時間 3,095 ms / 9,973 ms
コード長 4,305 bytes
コンパイル時間 3,568 ms
コンパイル使用メモリ 81,316 KB
実行使用メモリ 45,456 KB
最終ジャッジ日時 2024-11-16 23:04:44
合計ジャッジ時間 13,856 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.InputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.List;
import java.util.NoSuchElementException;

class FastScanner { // {{{
  private final InputStream in = System.in;
  private final byte[] buffer = new byte[1024];
  private int ptr = 0;
  private int buflen = 0;
  private boolean hasNextByte() {
    if(ptr < buflen) { return true; }
    ptr = 0;
    try {
      buflen = in.read(buffer);
    } catch(IOException ex) {
      ex.printStackTrace();
    }
    if(buflen <= 0) { return false; }
    return true;
  }
  private int readByte() { if(hasNextByte()) { return buffer[ptr++]; } return -1; }
  private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; }
  private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) { ptr++; } }
  public boolean hasNext() { skipUnprintable(); 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 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() {
    if(!hasNext()) { throw new NoSuchElementException(); }
    int 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();
    }
  }
} // }}}

final class MillerRabin {
  private static long modMul(long a, long b, long m) {
    a = Long.remainderUnsigned(a, m);
    b = Long.remainderUnsigned(b, m);
    long res = 0;
    for( ; b!=0; b>>=1) {
      if((b & 1) == 1) {
        res += a;
        if(Long.compareUnsigned(res, m) >= 0) { res -= m; }
      }
      a <<= 1;
      if(Long.compareUnsigned(a, m) >= 0) { a -= m; }
    }
    return res;
  }
  private static long modPow(long x, long k, long m) {
    if(k == 0) { return 1; }
    if((k & 1) == 1) { return modMul(x, modPow(x, k-1, m), m); }
    return modPow(modMul(x, x, m), k>>1, m);
  }
  public static boolean isPrime(long n) {
    if(n == 1) { return false; }
    List<Long> primes = Arrays.asList(new Long[]{2L, 3L, 5L, 7L, 11L, 13L, 17L, 19L, 23L, 29L, 31L, 37L});
    for(long p : primes) {
      if(n == p) { return true; }
      if(n % p == 0) { return false; } 
    }
    int s = 0; long d = n - 1;
    while((d & 1) == 0) { ++s; d>>=1; }
    List<Long> witness = Arrays.asList(new Long[]{2L, 325L, 9375L, 28178L, 450775L, 9780504L, 1795265022L});
    if(n < 1L<<32) { witness = Arrays.asList(new Long[]{2L, 7L, 61L}); }
    int loop;
    for(long a : witness) {
      if(Long.remainderUnsigned(a, n) == 0) { return true; }
      long x = modPow(a, d, n);
      if(Long.compareUnsigned(x, 1) == 0 || Long.compareUnsigned(x, n-1) == 0) { continue; }
      for(loop=1; loop<s; ++loop) {
        x = modMul(x, x, n);
        if(Long.compareUnsigned(x, n-1) == 0) { break; }
      }
      if(loop == s) { return false; }
    }
    return true;
  }
}

public class Main {
  private void solve() {
    FastScanner sc = new FastScanner();
    PrintWriter out = new PrintWriter(System.out);
    int n = sc.nextInt();
    for(int i=0; i<n; ++i) {
      long x = sc.nextLong();
      boolean yes = MillerRabin.isPrime(x);
      out.println(x + " " + (yes ? '1' : '0'));
    }
    out.flush();
  }

  public static void main(String[] args) {
    new Main().solve();
  }
}
0