結果
問題 | No.308 素数は通れません |
ユーザー |
|
提出日時 | 2015-12-01 20:33:20 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 81 ms / 1,000 ms |
コード長 | 3,863 bytes |
コンパイル時間 | 4,015 ms |
コンパイル使用メモリ | 80,112 KB |
実行使用メモリ | 37,432 KB |
最終ジャッジ日時 | 2024-11-27 18:16:57 |
合計ジャッジ時間 | 12,230 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 107 |
ソースコード
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintStream;import java.io.PrintWriter;import java.math.BigInteger;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.Deque;import java.util.Iterator;import java.util.List;public class Main_yukicoder308_1 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);Printer pr = new Printer(System.out);String N = sc.next();if (N.length() <= 2) {int n = Integer.parseInt(N);boolean[] notprime = new boolean[n + 1];notprime[1] = true;for (int i = 2; i * i <= n; i++) {if (!notprime[i]) {for (int j = 2; i * j <= n; j++) {notprime[i * j] = true;}}}for (int w = 2; w <= n; w++) {if (dfs(w, n, notprime, pr)) {pr.println(w);break;}}} else {int mod = 0;for (int i = 0; i < N.length(); i++) {mod = (10 * mod + (N.charAt(i) - '0')) % 8;}if (mod != 1) {pr.println(8);} else {if (isPrime(N, 8)) {pr.println(14);} else {pr.println(8);}}}pr.close();sc.close();}private static boolean isPrime(String N, int sub) {if (N.length() < 12) {long n = Long.parseLong(N);n -= sub;boolean prime = (n != 1);for (long i = 2; i * i <= n; i++) {if (n % i == 0) {prime = false;break;}}return prime;} else {BigInteger n = new BigInteger(N);n = n.subtract(new BigInteger(Integer.toString(sub)));return n.isProbablePrime(20);}}private static boolean dfs(int w, int n, boolean[] notprime, Printer pr) {int[] d = {w, 1, -1, -w};boolean[] used = new boolean[n + 1];Deque<Integer> st = new ArrayDeque<Integer>();Deque<List<Integer>> rt = new ArrayDeque<List<Integer>>();st.push(1);rt.push(new ArrayList<Integer>());used[1] = true;while (!st.isEmpty()) {int e = st.pop();List<Integer> tmprt = rt.pop();for (int i = 0; i < d.length; i++) {int tmp = e + d[i];if (tmp < 1 || tmp > n) {continue;}if (e % w == 0 && d[i] == 1) {continue;}if (e % w == 1 && d[i] == -1) {continue;}if (tmp == n) {tmprt.add(tmp);// pr.println(tmprt.toString());return true;}if (!used[tmp] && notprime[tmp]) {used[tmp] = true;st.push(tmp);List<Integer> tt = new ArrayList<Integer>(tmprt);tt.add(tmp);rt.push(tt);}}}return false;}@SuppressWarnings("unused")private static class Scanner {BufferedReader br;Iterator<String> it;Scanner (InputStream in) {br = new BufferedReader(new InputStreamReader(in));}String next() throws RuntimeException {try {if (it == null || !it.hasNext()) {it = Arrays.asList(br.readLine().split(" ")).iterator();}return it.next();} catch (IOException e) {throw new IllegalStateException();}}int nextInt() throws RuntimeException {return Integer.parseInt(next());}long nextLong() throws RuntimeException {return Long.parseLong(next());}float nextFloat() throws RuntimeException {return Float.parseFloat(next());}double nextDouble() throws RuntimeException {return Double.parseDouble(next());}void close() {try {br.close();} catch (IOException e) {// throw new IllegalStateException();}}}private static class Printer extends PrintWriter {Printer(PrintStream out) {super(out);}}}