T1：倍数序列3
本题难度中等，思路和 LIS 类似，用 dp[i] 表示以 \(a_i\) 结尾的倍数序列的个数。如果 \(a_i\) 是 \(a_j\) 的倍数，倍数序列个数就是 \(dp[j]\)，枚举所有 \(j\) 求和即可得到 \(dp[i]\) 。时间复杂度：\(O(n^2)\)
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<ll> a(n);
rep(i, n) cin >> a[i];
sort(a.begin(), a.end());
ll ans = 0;
vector<ll> dp(n);
rep(i, n) {
dp[i] = 1;
rep(j, i) if (a[i]%a[j] == 0) {
dp[i] += dp[j];
}
ans += dp[i];
}
cout << ans << '\n';
return 0;
}