結果
問題 | No.979 Longest Divisor Sequence |
ユーザー | ゆにぽけ |
提出日時 | 2023-10-26 00:45:16 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 152 ms / 2,000 ms |
コード長 | 2,237 bytes |
コンパイル時間 | 1,485 ms |
コンパイル使用メモリ | 135,604 KB |
実行使用メモリ | 9,216 KB |
最終ジャッジ日時 | 2024-09-25 08:44:57 |
合計ジャッジ時間 | 2,553 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 12 ms
6,912 KB |
testcase_01 | AC | 12 ms
6,912 KB |
testcase_02 | AC | 12 ms
6,912 KB |
testcase_03 | AC | 12 ms
6,912 KB |
testcase_04 | AC | 12 ms
6,912 KB |
testcase_05 | AC | 12 ms
7,040 KB |
testcase_06 | AC | 12 ms
6,912 KB |
testcase_07 | AC | 13 ms
6,912 KB |
testcase_08 | AC | 13 ms
7,040 KB |
testcase_09 | AC | 12 ms
6,912 KB |
testcase_10 | AC | 15 ms
8,064 KB |
testcase_11 | AC | 15 ms
8,320 KB |
testcase_12 | AC | 15 ms
8,192 KB |
testcase_13 | AC | 40 ms
8,192 KB |
testcase_14 | AC | 152 ms
9,216 KB |
testcase_15 | AC | 59 ms
8,576 KB |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cstring> #include<cassert> #include<cmath> #include<ctime> #include<iomanip> #include<numeric> #include<stack> #include<queue> #include<map> #include<unordered_map> #include<set> #include<unordered_set> #include<bitset> #include<random> #include<functional> #include<utility> using namespace std; struct Eratosthenes { vector<int> isp,minfactor,myprime,moebius; Eratosthenes (int n) : isp(n+1,1),minfactor(n+1,__INT_MAX__),moebius(n+1,1){ isp[0] = isp[1] = 0; minfactor[0] = 0;minfactor[1] = 1; for(int p = 2;p <= n;p++){ if(!isp[p]) continue; minfactor[p] = p; moebius[p] = -1; myprime.push_back(p); for(int q = 2*p;q <= n;q += p){ isp[q] = false; if(!((q/p)%p)) moebius[q] = 0; else moebius[q] = -moebius[q]; minfactor[q] = min(minfactor[q],p); } } } vector<pair<int,int>> prime_factorize(int n) { vector<pair<int,int>> res; while(n-1){ int p = minfactor[n]; int exp = 0; while(minfactor[n] == p){ n /= p; exp ++; } res.push_back(make_pair(p,exp)); } return res; } vector<int> divisors(int n){ vector<int> res; res.push_back(1); auto pf = prime_factorize(n); for(auto [p,e]:pf){ int s = (int)res.size(); for(int i = 0;i < s;i++){ int v = 1; for(int j = 0;j < e;j++){ v *= p; res.push_back(res[i]*v); } } } return res; } }; Eratosthenes er((int)3e5); int N,A[3 << 17],dp[3 << 17]; void solve() { cin >> N; for(int i = 0;i < N;i++) { cin >> A[i]; dp[A[i]] = max(dp[A[i]],1); for(int D:er.divisors(A[i]))if(D < A[i]) dp[A[i]] = max(dp[A[i]],dp[D]+1); } int ans = 0; for(int i = 0;i < N;i++) ans = max(ans,dp[A[i]]); cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; //cin >> tt; while(tt--) solve(); }