結果
問題 | No.979 Longest Divisor Sequence |
ユーザー |
![]() |
提出日時 | 2020-01-31 22:47:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 624 ms / 2,000 ms |
コード長 | 1,102 bytes |
コンパイル時間 | 2,464 ms |
コンパイル使用メモリ | 119,608 KB |
最終ジャッジ日時 | 2025-01-08 21:22:21 |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <deque> #include <queue> #include <array> #include <set> #include <map> #include <cmath> #include <complex> #include <algorithm> #include <numeric> #include <utility> #include <tuple> #include <functional> #include <bitset> #include <cstdint> #include <cassert> #include <random> using namespace std; using i64 = int64_t; using i32 = int32_t; template<class T> T iabs(const T& x) { return max(x, -x); } unsigned char b[300001]; int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } for (int i = 0; i < n; ++i) { b[a[i]] = a[i] == 1 ? 1 : b[1] + 1; for (int x = 2; x * x <= a[i]; ++x) { if (a[i] % x == 0) { b[a[i]] = max(b[a[i]], (unsigned char)(b[x] + 1)); b[a[i]] = max(b[a[i]], (unsigned char)(b[a[i] / x] + 1)); } } } int ans = 0; for (int i = 1; i <= 300000; ++i) { ans = max(ans, int(b[i])); } cout << ans << endl; return 0; }