結果
問題 | No.12 限定された素数 |
ユーザー | uwi |
提出日時 | 2015-02-18 21:55:15 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 473 ms / 5,000 ms |
コード長 | 5,610 bytes |
コンパイル時間 | 4,161 ms |
コンパイル使用メモリ | 84,084 KB |
実行使用メモリ | 64,984 KB |
最終ジャッジ日時 | 2024-05-03 09:08:30 |
合計ジャッジ時間 | 15,943 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 368 ms
64,580 KB |
testcase_01 | AC | 380 ms
63,888 KB |
testcase_02 | AC | 351 ms
64,008 KB |
testcase_03 | AC | 354 ms
64,088 KB |
testcase_04 | AC | 392 ms
63,972 KB |
testcase_05 | AC | 455 ms
63,964 KB |
testcase_06 | AC | 378 ms
63,836 KB |
testcase_07 | AC | 385 ms
64,388 KB |
testcase_08 | AC | 411 ms
64,196 KB |
testcase_09 | AC | 392 ms
63,788 KB |
testcase_10 | AC | 391 ms
64,048 KB |
testcase_11 | AC | 398 ms
64,344 KB |
testcase_12 | AC | 390 ms
64,208 KB |
testcase_13 | AC | 379 ms
64,832 KB |
testcase_14 | AC | 397 ms
64,216 KB |
testcase_15 | AC | 380 ms
64,044 KB |
testcase_16 | AC | 402 ms
64,168 KB |
testcase_17 | AC | 377 ms
64,712 KB |
testcase_18 | AC | 374 ms
64,340 KB |
testcase_19 | AC | 360 ms
64,372 KB |
testcase_20 | AC | 353 ms
64,064 KB |
testcase_21 | AC | 324 ms
63,908 KB |
testcase_22 | AC | 347 ms
64,608 KB |
testcase_23 | AC | 340 ms
64,984 KB |
testcase_24 | AC | 427 ms
64,384 KB |
testcase_25 | AC | 473 ms
64,512 KB |
ソースコード
package q0xx; import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; public class Q34 { static InputStream is; static PrintWriter out; static String INPUT = ""; static void solve() { int[] primes = sieveEratosthenesL(5000000); int[] pptn = new int[5000001]; for(int i = 0;i < primes.length;i++){ int x = primes[i]; int lptn = 0; while(x > 0){ lptn |= 1<<x%10; x /= 10; } pptn[primes[i]] = lptn; } int n = ni(); int ptn = 0; for(int i = 0;i < n;i++){ ptn |= 1<<ni(); } int[] f = new int[10]; int tail = 1; int maxlen = -1; outer: for(int head = 1;head <= 5000000;head++){ for(int j = 0;j <= 9;j++){ if(pptn[head]<<~j<0)f[j]++; } inner: while(true){ for(int j = 0;j <= 9;j++){ if(f[j] > 0 && ptn<<~j>=0){ for(int k = 0;k <= 9;k++){ if(pptn[tail]<<~k<0)f[k]--; } tail++; continue inner; } } break; } for(int j = 0;j <= 9;j++){ if((f[j] > 0) != (ptn<<~j<0))continue outer; } maxlen = Math.max(maxlen, head-tail); } out.println(maxlen); } public static int[] sieveEratosthenesL(int n) { if(n <= 64){ int[] primes = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61}; for(int i = 0;i < primes.length;i++){ if(n < primes[i]){ return Arrays.copyOf(primes, i); } } return primes; } int u = n+64; double lu = Math.log(u); int[] ret = new int[(int)(u/lu+u/lu/lu*1.5)]; ret[0] = 2; int pos = 1; long[] isnp = new long[(n+1)/64/2+1]; int sup = (n+1)/64/2+1; int[] tprimes = {3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61}; for(int tp : tprimes){ ret[pos++] = tp; long[] ptn = new long[tp]; for(int i = (tp-3)/2;i < tp<<6;i+=tp)ptn[i>>6] |= 1L<<i; for(int j = 0;j < sup;j += tp){ for(int i = 0;i < tp && i+j < sup;i++){ isnp[j+i] |= ptn[i]; } } } // 3,5,7 // 2x+3=n final int[] magic = {0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28, 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11, 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10, 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12}; int h = n/2; for(int i = 0;i < sup;i++){ for(long j = ~isnp[i];j != 0;j &= j-1){ int pp = i<<6|magic[(int)((j&-j)*0x022fdd63cc95386dL>>>58)]; int p = 2*pp+3; if(p > n)break; ret[pos++] = p; if((long)p*p > n)continue; for(int q = (p*p-3)/2;q <= h;q += p)isnp[q>>6] |= 1L<<q; } } return Arrays.copyOf(ret, pos); } public static void main(String[] args) throws Exception { long S = System.currentTimeMillis(); is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); solve(); out.flush(); long G = System.currentTimeMillis(); tr(G-S+"ms"); } private static boolean eof() { if(lenbuf == -1)return true; int lptr = ptrbuf; while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false; try { is.mark(1000); while(true){ int b = is.read(); if(b == -1){ is.reset(); return true; }else if(!isSpaceChar(b)){ is.reset(); return false; } } } catch (IOException e) { return true; } } private static byte[] inbuf = new byte[1024]; static int lenbuf = 0, ptrbuf = 0; private static int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private static double nd() { return Double.parseDouble(ns()); } private static char nc() { return (char)skip(); } private static String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ') sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private static char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private static char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private static int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private static int ni() { int num = 0, b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); } }