結果
| 問題 | No.3030 ミラー・ラビン素数判定法のテスト |
| ユーザー |
 viral8
|
| 提出日時 | 2023-07-12 20:46:25 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 959 ms / 9,973 ms |
| コード長 | 9,447 bytes |
| コンパイル時間 | 2,655 ms |
| コンパイル使用メモリ | 80,560 KB |
| 実行使用メモリ | 65,368 KB |
| 最終ジャッジ日時 | 2023-10-12 10:50:44 |
| 合計ジャッジ時間 | 8,260 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 43 ms
49,288 KB |
| testcase_01 | AC | 42 ms
49,240 KB |
| testcase_02 | AC | 50 ms
50,252 KB |
| testcase_03 | AC | 59 ms
49,784 KB |
| testcase_04 | AC | 812 ms
64,088 KB |
| testcase_05 | AC | 790 ms
63,260 KB |
| testcase_06 | AC | 630 ms
63,948 KB |
| testcase_07 | AC | 769 ms
65,368 KB |
| testcase_08 | AC | 440 ms
60,732 KB |
| testcase_09 | AC | 959 ms
61,700 KB |
ソースコード
import java.io.InputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.math.BigInteger;
import java.awt.Point;
import java.util.*;
public final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
int n = sc.nextInt();
while(n-->0){
long num = sc.nextLong();
out.print(num);
out.println(isPrime(num)?" 1":" 0");
}
out.close();
}
public static boolean isPrime(long n){
n = Math.abs(n);
if(n==2)
return true;
if(n==1||(n&1)==0)
return false;
long d = n-1;
while((d&1)==0)
d >>= 1;
for(long a:new long[]{2,7,61,325,9375,28178,450775,9780504,1795265022}){
if(a>=n)
return true;
long t = d;
long y = bigModPow(a,t,n);
while(t<n-1&&y!=1&&y!=n-1){
y = bigModPow(y,2,n);
t <<= 1;
}
if(y!=n-1&&(t&1)==0)
return false;
}
return true;
}
private static long bigModPow(long a,long b,long m){
return BigInteger.valueOf(a).modPow(BigInteger.valueOf(b),BigInteger.valueOf(m)).longValue();
}
}
/*
／￣＼
| |
＼＿／
|
／ ￣ ￣ ＼
／ ＼ ／ ＼
／ ⌒ ⌒ ＼ よくぞこの提出結果を開いてくれた
| （__人__） | 褒美としてオプーナを買う権利をやる
＼ ｀⌒´ ／ ☆
/ヽ､--ー､＿＿, -‐ ´ ＼─／
／ > ヽ▼●▼<＼ ||ｰ､.
/ヽ､ ＼ i |｡| |/ ヽ (ニ､`ヽ.
l ヽ l |｡| | r-､y ｀ﾆ ﾉ ＼
l | |ー─ | ￣ l ｀~ヽ＿ノ＿_
／￣￣￣￣ヽ-'ヽ--' ／ オープナ ／|
|￣￣￣￣￣￣|／| |￣￣￣￣￣￣|／| ＿＿＿＿＿＿
／￣オプーナ／|￣|__｣／_オープナ ／|￣|__,」＿_ ／|
|￣￣￣￣￣|／オープナ￣／￣￣￣￣|／オプーナ ／| ／ |
|￣￣￣￣￣|￣￣￣￣￣|／l￣￣￣￣|￣￣￣￣￣|／| ／
|￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|
*/
/*////////////////////////////////////////////////
* My Library *
@author viral
*/////////////////////////////////////////////////
// MyScanner
final class SimpleScanner {
final private int buff_size = 1 << 12;
private final InputStream is;
private final byte[] buff;
private int point, length;
public SimpleScanner ( InputStream is ) {
this.is = is;
buff = new byte[buff_size];
point = length = 0;
}
private void reload () {
do {
try {
length = is.read( buff, point = 0, buff_size );
} catch ( IOException e ) {
e.printStackTrace();
System.exit( 1 );
}
} while ( length == -1 );
}
private byte read () {
if ( point == length ) {
reload();
}
return buff[point++];
}
public byte nextByte () {
byte c = read();
while ( c <= ' ' ) {
c = read();
}
return c;
}
public int nextInt () {
int ans = 0;
byte c = read();
while ( c <= ' ' ) {
c = read();
}
boolean negate = c == '-';
if ( c == '-' ) {
c = read();
}
while ( '0' <= c && c <= '9' ) {
ans = ans * 10 + c - '0';
c = read();
}
return negate ? -ans : ans;
}
public long nextLong () {
long ans = 0;
byte c = read();
while ( c <= ' ' ) {
c = read();
}
boolean negate = c == '-';
if ( c == '-' ) {
c = read();
}
while ( '0' <= c && c <= '9' ) {
ans = ans * 10 + c - '0';
c = read();
}
return negate ? -ans : ans;
}
public char nextChar () {
byte c = read();
while ( c <= ' ' ) {
c = read();
}
return ( char )c;
}
public String next () {
StringBuilder ans = new StringBuilder();
byte c = read();
while ( c <= ' ' ) {
c = read();
}
while ( c > ' ' ) {
ans.append( ( char )c );
c = read();
}
return ans.toString();
}
public byte[] nextByte ( int n ) {
byte[] ans = new byte[n];
for ( int i = 0; i < n; ++i ) {
ans[i] = nextByte();
}
return ans;
}
public int[] nextInt ( int n ) {
int[] ans = new int[n];
for ( int i = 0; i < n; ++i ) {
ans[i] = nextInt();
}
return ans;
}
public long[] nextLong ( int n ) {
long[] ans = new long[n];
for ( int i = 0; i < n; ++i ) {
ans[i] = nextLong();
}
return ans;
}
public String[] next ( int n ) {
String[] ans = new String[n];
for ( int i = 0; i < n; ++i ) {
ans[i] = next();
}
return ans;
}
public byte[][] nextByte ( int n, int m ) {
byte[][] ans = new byte[n][];
for ( int i = 0; i < n; ++i ) {
ans[i] = nextByte( m );
}
return ans;
}
public int[][] nextInt ( int n, int m ) {
int[][] ans = new int[n][];
for ( int i = 0; i < n; ++i ) {
ans[i] = nextInt( m );
}
return ans;
}
public long[][] nextLong ( int n, int m ) {
long[][] ans = new long[n][];
for ( int i = 0; i < n; ++i ) {
ans[i] = nextLong( m );
}
return ans;
}
public String[][] next ( int n, int m ) {
String[][] ans = new String[n][];
for ( int i = 0; i < n; ++i ) {
ans[i] = next( m );
}
return ans;
}
public char[] nextCharArray () {
return next().toCharArray();
}
public char[][] nextCharArray ( int n ) {
char[][] ans = new char[n][];
for ( int i = 0; i < n; ++i ) {
ans[i] = nextCharArray();
}
return ans;
}
public int[][] nextGraph ( int N, int M ) {
if ( M == 0 ) {
return new int[N + 1][0];
}
int[][] ans = new int[N + 1][];
int[] count = new int[N + 1];
int[][] path = nextInt( M, 2 );
for ( int[] temp: path ) {
++count[temp[0]];
++count[temp[1]];
}
for ( int i = 1; i <= N; ++i ) {
ans[i] = new int[count[i]];
}
for ( int[] temp: path ) {
ans[temp[0]][--count[temp[0]]] = temp[1];
ans[temp[1]][--count[temp[1]]] = temp[0];
}
ans[0] = new int[0];
return ans;
}
public Point nextPoint () {
return new Point( nextInt(), nextInt() );
}
public Point[] nextPoint ( int n ) {
Point[] ans = new Point[n];
for ( int i = 0; i < n; ++i ) {
ans[i] = nextPoint();
}
return ans;
}
public void close () {
try {
is.close();
} catch ( IOException e ) {
e.printStackTrace();
System.exit( 1 );
}
}
}
// MyPrinter
final class SimplePrinter extends PrintWriter {
public SimplePrinter ( PrintStream os ) {
super( os );
}
public SimplePrinter ( PrintStream os, boolean bool ) {
super( os, bool );
}
public void println ( int[] array ) {
println( array, ' ' );
}
public void println ( int[] array, String str ) {
print( array[0] );
for ( int i = 1; i < array.length; ++i ) {
print( str );
print( array[i] );
}
println();
}
public void println ( int[] array, char c ) {
print( array[0] );
for ( int i = 1; i < array.length; ++i ) {
print( c );
print( array[i] );
}
println();
}
public void println ( int[][] array ) {
println( array, ' ' );
}
public void println ( int[][] arrays, String str ) {
for ( int[] array: arrays ) {
println( array, str );
}
}
public void println ( int[][] arrays, char c ) {
for ( int[] array: arrays ) {
println( array, c );
}
}
public void println ( long[] array ) {
println( array, ' ' );
}
public void println ( long[] array, String str ) {
print( array[0] );
for ( int i = 1; i < array.length; ++i ) {
print( str );
print( array[i] );
}
println();
}
public void println ( long[] array, char c ) {
print( array[0] );
for ( int i = 1; i < array.length; ++i ) {
print( c );
print( array[i] );
}
println();
}
public void println ( long[][] array ) {
println( array, ' ' );
}
public void println ( long[][] arrays, String str ) {
for ( long[] array: arrays ) {
println( array, str );
}
}
public void println ( long[][] arrays, char c ) {
for ( long[] array: arrays ) {
println( array, c );
}
}
public void println ( char[] cs, String str ) {
print( cs[0] );
for ( int i = 1; i < cs.length; ++i ) {
print( str );
print( cs[i] );
}
println();
}
public void println ( char[] cs, char c ) {
print( cs[0] );
for ( int i = 1; i < cs.length; ++i ) {
print( c );
print( cs[i] );
}
println();
}
public void println ( char[][] cs ) {
for ( char[] c: cs ) {
println( c );
}
}
public void println ( char[][] cs, String str ) {
print( cs[0] );
for ( int i = 1; i < cs.length; ++i ) {
print( str );
print( cs[i] );
}
println();
}
public void println ( char[][] cs, char c ) {
print( cs[0] );
for ( int i = 1; i < cs.length; ++i ) {
print( c );
print( cs[i] );
}
println();
}
public <E> void println ( E[] array ) {
println( array, ' ' );
}
public <E> void println ( E[] array, String str ) {
print( array[0] );
for ( int i = 1; i < array.length; ++i ) {
print( str );
print( array[i] );
}
println();
}
public <E> void println ( E[] array, char c ) {
print( array[0] );
for ( int i = 1; i < array.length; ++i ) {
print( c );
print( array[i] );
}
println();
}
public <E> void println ( E[][] arrays ) {
println( arrays, ' ' );
}
public <E> void println ( E[][] arrays, String str ) {
for ( E[] array: arrays ) {
println( array, str );
}
}
public <E> void println ( E[][] arrays, char c ) {
for ( E[] array: arrays ) {
println( array, c );
}
}
}