結果
| 問題 | No.826 連絡網 |
| コンテスト | |
| ユーザー |
 kusomushi
|
| 提出日時 | 2019-07-08 21:07:56 |
| 言語 | Java (openjdk 23) |
| 結果 |
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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 10 TLE * 1 -- * 19 |
ソースコード
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;
}
}