牛客IOI周赛23-普及组 D.小L的数列(dp)

Description

一句话题意：给出一个数字序列 ，找出最长的序列 满足：

Solution

这里给出一个 的做法,
由于 , 可以通过本题。
对于 先排序，这样可以满足 的要求。
随后从小到大做质因数分解，不妨令 为当前质因子 所能构造的最长序列，
那么当遍历到每个数字 时，都能使得它的质因子 成为 , 其中 为 的质因子。
直观的感受就是从前面取结尾具有某个相同质因子的最长的一段添上当前的数字。
实际上可以先筛出 里面的质因子，进一步优化复杂度，但是对于本题没必要。

Code

#include<bits/stdc++.h>

typedef long long ll;
using namespace std;
const int N = 2e5 + 5;
const int mod = 998244353;

void solve() {
  int n; cin >> n;
  vector<int> a(n), dp(int(1e5 + 5), 0);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  for (int i = 0; i < n; i++) {
    int pre = a[i], res = 0;
    vector<int> factor;
    for (int j = 2; 1LL * j * j <= pre; j++) {
      if (pre % j == 0) {
        res = max(res, dp[j]);
        while (pre % j == 0) {
          pre /= j;
        }
        factor.emplace_back(j);
      }
    }
    if (pre > 1) {
      res = max(res, dp[pre]);
      factor.emplace_back(pre);
    }
    for (auto &x : factor) {
      dp[x] = res + 1;
    }
  }
  cout << *max_element(dp.begin(), dp.end()) << '\n'; 
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0);
  int T = 1; cin >> T;
  while(T--) {
    solve();
  }
  return 0;
}