結果
問題 | No.979 Longest Divisor Sequence |
ユーザー | lavox |
提出日時 | 2021-12-02 20:24:06 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 763 ms / 2,000 ms |
コード長 | 3,572 bytes |
コンパイル時間 | 2,587 ms |
コンパイル使用メモリ | 80,056 KB |
実行使用メモリ | 101,508 KB |
最終ジャッジ日時 | 2024-07-05 02:04:48 |
合計ジャッジ時間 | 10,951 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 400 ms
87,068 KB |
testcase_01 | AC | 390 ms
87,024 KB |
testcase_02 | AC | 403 ms
87,216 KB |
testcase_03 | AC | 408 ms
87,100 KB |
testcase_04 | AC | 409 ms
87,288 KB |
testcase_05 | AC | 394 ms
87,100 KB |
testcase_06 | AC | 396 ms
87,200 KB |
testcase_07 | AC | 400 ms
87,200 KB |
testcase_08 | AC | 427 ms
87,212 KB |
testcase_09 | AC | 403 ms
87,152 KB |
testcase_10 | AC | 449 ms
87,132 KB |
testcase_11 | AC | 471 ms
87,136 KB |
testcase_12 | AC | 440 ms
87,772 KB |
testcase_13 | AC | 466 ms
89,856 KB |
testcase_14 | AC | 763 ms
101,508 KB |
testcase_15 | AC | 582 ms
94,320 KB |
ソースコード
import java.io.IOException; import java.io.InputStream; import java.util.ArrayList; import java.util.Arrays; import java.util.NoSuchElementException; public class Main { public static void main(String[] args) { Main o = new Main(); o.solve(); } public void solve() { FastScanner sc = new FastScanner(System.in); int N = sc.nextInt(); int[] A = new int[N]; for (int i = 0; i < N; i++) { A[i] = sc.nextInt(); } int AMAX = 300001; ArrayList<Integer>[] factor = new ArrayList[AMAX]; for (int i = 0; i < AMAX; i++) { factor[i] = new ArrayList<>(); } boolean[] p = new boolean[AMAX]; Arrays.fill(p, true); for (int i = 2; i < AMAX; i++) { if ( !p[i] ) continue; int cur = i; factor[i].add(i); while ( (cur += i) < AMAX ) { p[cur] = false; factor[cur].add(i); } } int[] max = new int[AMAX]; //max[1] = 1; for (int i = 0; i < N; i++) { int[] pow = new int[factor[A[i]].size()]; int cnt = 1; int a = A[i]; for (int j = 0; j < factor[A[i]].size(); j++) { int pr = factor[A[i]].get(j); while ( a % pr == 0 ) { pow[j]++; a /= pr; } cnt *= (pow[j] + 1); } int[] d = new int[cnt]; divisor(factor[A[i]], pow, 0, 1, 0, d); if ( A[i] == 1 ) { max[1] = 1; } else { int m = max[A[i]]; for ( int f : d ) { if ( f == A[i] ) continue; m = Math.max(m, max[f] + 1); } max[A[i]] = m; } } int ans = 0; for (int i = 0; i < AMAX; i++) { ans = Math.max(max[i], ans); } System.out.println(ans); } int divisor(ArrayList<Integer> f, int[] pow, int cur, int num, int i, int[] div) { if ( cur >= pow.length ) { div[i++] = num; return i; } for (int j = 0; j <= pow[cur]; j++) { i = divisor(f, pow, cur + 1, num, i, div); num *= f.get(cur); } return i; } class FastScanner { private final InputStream in; private final byte[] buf = new byte[1024]; private int ptr = 0; private int buflen = 0; FastScanner( InputStream source ) { this.in = source; } private boolean hasNextByte() { if ( ptr < buflen ) return true; else { ptr = 0; try { buflen = in.read(buf); } catch (IOException e) { e.printStackTrace(); } if ( buflen <= 0 ) return false; } return true; } private int readByte() { if ( hasNextByte() ) return buf[ptr++]; else return -1; } private boolean isPrintableChar( int c ) { return 33 <= c && c <= 126; } private boolean isNumeric( int c ) { return '0' <= c && c <= '9'; } private void skipToNextPrintableChar() { while ( hasNextByte() && !isPrintableChar(buf[ptr]) ) ptr++; } public boolean hasNext() { skipToNextPrintableChar(); return hasNextByte(); } public String next() { if ( !hasNext() ) throw new NoSuchElementException(); StringBuilder ret = new StringBuilder(); int b = readByte(); while ( isPrintableChar(b) ) { ret.appendCodePoint(b); b = readByte(); } return ret.toString(); } public long nextLong() { if ( !hasNext() ) throw new NoSuchElementException(); long ret = 0; int b = readByte(); boolean negative = false; if ( b == '-' ) { negative = true; if ( hasNextByte() ) b = readByte(); } if ( !isNumeric(b) ) throw new NumberFormatException(); while ( true ) { if ( isNumeric(b) ) ret = ret * 10 + b - '0'; else if ( b == -1 || !isPrintableChar(b) ) return negative ? -ret : ret; else throw new NumberFormatException(); b = readByte(); } } public int nextInt() { return (int)nextLong(); } public double nextDouble() { return Double.parseDouble(next()); } } }