結果
問題 | No.826 連絡網 |
ユーザー | kusomushi |
提出日時 | 2019-07-08 21:07:56 |
言語 | Java21 (openjdk 21) |
結果 |
TLE
|
実行時間 | - |
コード長 | 10,556 bytes |
コンパイル時間 | 2,932 ms |
コンパイル使用メモリ | 95,528 KB |
実行使用メモリ | 112,132 KB |
最終ジャッジ日時 | 2024-10-09 13:26:49 |
合計ジャッジ時間 | 7,694 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 55 ms
56,988 KB |
testcase_01 | AC | 56 ms
50,432 KB |
testcase_02 | AC | 57 ms
50,532 KB |
testcase_03 | AC | 107 ms
52,096 KB |
testcase_04 | AC | 119 ms
54,412 KB |
testcase_05 | AC | 90 ms
51,920 KB |
testcase_06 | AC | 93 ms
51,828 KB |
testcase_07 | AC | 115 ms
54,448 KB |
testcase_08 | AC | 96 ms
51,656 KB |
testcase_09 | AC | 118 ms
54,436 KB |
testcase_10 | AC | 69 ms
51,296 KB |
testcase_11 | AC | 104 ms
52,124 KB |
testcase_12 | TLE | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
ソースコード
import java.io.*; import java.util.*; public class Main { static int N, P; public static void main(String[] args) { FastScanner sc = new FastScanner(System.in); N = sc.nextInt(); P = sc.nextInt(); System.out.println(solve()); } static int solve() { Eratos sieve = new Eratos(N); boolean[] done = new boolean[N+1]; Set<Edge> edges = new HashSet<>(); for (int i = 1; i <= N; i++) { long[] factors = sieve.enumUniqFactors(i); for (int u = 0; u < factors.length-1; u++) { for (int v = u+1; v < factors.length; v++) { edges.add( new Edge((int)factors[u], (int)factors[v]) ); } } } Edge[][] G = adjB(N+1, edges); Set<Integer> used = new HashSet<>(); int[] q = new int[N]; int u = 0, v = 0; for (long pp : sieve.enumUniqFactors(P)) { q[v++] = (int)pp; used.add((int)pp); } while( u != v ) { int a = q[u++]; for (Edge e : G[a]) { int b = e.a == a ? e.b : e.a; if( !used.contains(b) ) { q[v++] = b; used.add(b); } } } int ans = 0; lo: for (int i = 1; i <= N; i++) { long[] factors = sieve.enumUniqFactors(i); for (long factor : factors) { if( used.contains((int)factor) ) { ans++; continue lo; } } } return ans; } static Edge[][] adjB(int n, Set<Edge> E) { Edge[][] adj = new Edge[n][]; int[] cnt = new int[n]; for (Edge e : E) { cnt[e.a]++; cnt[e.b]++; } for (int i = 0; i < n; i++) { adj[i] = new Edge[cnt[i]]; } for (Edge e : E) { adj[e.a][--cnt[e.a]] = e; adj[e.b][--cnt[e.b]] = e; } return adj; } static class Edge { int a, b; public Edge(int a, int b) { this.a = a; this.b = b; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Edge edge = (Edge) o; return a == edge.a && b == edge.b; } @Override public int hashCode() { return Objects.hash(a, b); } } static class Eratos { static int[] mkSqrtPrimes(long n) { long root_L = (long)Math.sqrt(n); if( root_L > 10_000_000 ) throw new IllegalArgumentException("too big : " + n); int root = (int)root_L; boolean[] sieve = new boolean[root+1]; Arrays.fill(sieve, true); sieve[0] = false; sieve[1] = false; for (int i = 2; i <= root; i++) { if( sieve[i] ) { for (int d = 2; d*i <= root; d++) { sieve[i*d] = false; } } } int cnt = 0; for (boolean prime : sieve) { if( prime ) cnt++; } int[] primes = new int[cnt]; int idx = 0; for (int num = 2; num < sieve.length; num++) { if( sieve[num] ) { primes[idx++] = num; } } return primes; } static int factorSize(long n) { // 6: 2 * 3 * 5 * 7 * 11 * 13 = 30030 // 7: 2 * 3 * 5 * 7 * 11 * 13 * 17 = 510510 // 8: 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 = 9699690 // 9: 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 = 223_092_870 // 10: 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 6_469_693_230 // 11: 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 = 200_560_490_130 if( n <= 2*3*5*7*11*13 ) { return 6; } else if( n <= 2*3*5*7*11*13*17 ) { return 7; } else if( n <= 2L*3*5*7*11*13*17*19 ) { return 8; } else if( n <= 2L*3*5*7*11*13*17*19*23 ) { return 9; } else if( n <= 2L*3*5*7*11*13*17*19*23*29 ) { return 10; } else if( n <= 2L*3*5*7*11*13*17*19*23*29*31 ) { return 11; } else { return 12; } } long n; int[] sqrtPrimes; int factorSize; // cache long[] factors; long[][] factorCnts; Eratos(long n) { this.n = n; this.sqrtPrimes = mkSqrtPrimes(n); this.factorSize = factorSize(n); this.factors = new long[this.factorSize]; this.factorCnts = new long[this.factorSize][2]; } long[] enumUniqFactors(long n) { Arrays.fill(factors, 0); int i = 0; for (int p : sqrtPrimes) { if( n % p == 0 ) { factors[i++] = p; n /= p; while( n % p == 0 ) { n /= p; } } } if( n != 1 ) { factors[i++] = n; } return Arrays.copyOf(factors, i); } long[][] enumFactorCounts(long n) { for (long[] fc : factorCnts) { fc[0] = 0; fc[1] = 0; } int i = 0; for (int p : sqrtPrimes) { if( n < p ) break; int cnt = 0; while( n % p == 0 ) { n/=p; cnt++; } if( cnt > 0 ) { factorCnts[i][0] = p; factorCnts[i][1] = cnt; i++; } } if( n != 1 ) { factorCnts[i][0] = n; factorCnts[i][1] = 1; i++; } return Arrays.copyOf(factorCnts, i); } Map<Long, Integer> mapFactorCounts(long n) { long[][] arr = enumFactorCounts(n); Map<Long, Integer> map = new HashMap<>(); for (long[] fc : arr) { map.put(fc[0], (int)fc[1]); } return map; } } @SuppressWarnings("unused") static class FastScanner { private BufferedReader reader; private StringTokenizer tokenizer; FastScanner(InputStream in) { reader = new BufferedReader(new InputStreamReader(in)); tokenizer = null; } String next() { if (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } String nextLine() { if (tokenizer == null || !tokenizer.hasMoreTokens()) { try { return reader.readLine(); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken("\n"); } long nextLong() { return Long.parseLong(next()); } int nextInt() { return Integer.parseInt(next()); } int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } int[] nextIntArray(int n, int delta) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt() + delta; return a; } long[] nextLongArray(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nextLong(); return a; } } static void writeLines(int[] as) { PrintWriter pw = new PrintWriter(System.out); for (int a : as) pw.println(a); pw.flush(); } static void writeLines(long[] as) { PrintWriter pw = new PrintWriter(System.out); for (long a : as) pw.println(a); pw.flush(); } static void writeSingleLine(int[] as) { PrintWriter pw = new PrintWriter(System.out); for (int i = 0; i < as.length; i++) { if (i != 0) pw.print(" "); pw.print(as[i]); } pw.println(); pw.flush(); } static int max(int... as) { int max = Integer.MIN_VALUE; for (int a : as) max = Math.max(a, max); return max; } static int min(int... as) { int min = Integer.MAX_VALUE; for (int a : as) min = Math.min(a, min); return min; } static void debug(Object... args) { StringJoiner j = new StringJoiner(" "); for (Object arg : args) { if (arg == null) j.add("null"); else if (arg instanceof int[]) j.add(Arrays.toString((int[]) arg)); else if (arg instanceof long[]) j.add(Arrays.toString((long[]) arg)); else if (arg instanceof double[]) j.add(Arrays.toString((double[]) arg)); else if (arg instanceof Object[]) j.add(Arrays.toString((Object[]) arg)); else j.add(arg.toString()); } System.err.println(j.toString()); } static void printSingleLine(int[] array) { PrintWriter pw = new PrintWriter(System.out); for (int i = 0; i < array.length; i++) { if (i != 0) pw.print(" "); pw.print(array[i]); } pw.println(); pw.flush(); } static int lowerBound(int[] array, int value) { int lo = 0, hi = array.length, mid; while (lo < hi) { mid = (hi + lo) / 2; if (array[mid] < value) lo = mid + 1; else hi = mid; } return lo; } static int upperBound(int[] array, int value) { int lo = 0, hi = array.length, mid; while (lo < hi) { mid = (hi + lo) / 2; if (array[mid] <= value) lo = mid + 1; else hi = mid; } return lo; } }