题目
Polycarp 在街上发现了一个包含 n 个元素的数组。
Polycarp 发明了他的阵列美感标准。如果每对不同的索引 i≠j 必须满足以下条件中的至少一个，他就称数组为美数组：
ai 可被 aj 整除；
或 aj 可被 ai 整除。
例如，如果：
n=5 and a=[7,9,3,14,63]，则a数组不美观（对于i=4 and j=2，以上条件都不满足）；
n=3 且 a=[2,14,42]，则 a 数组很漂亮；
n=4 且 a=[45,9,3,18]，则 a 数组不美观（对于 i=1 和 j=4，上述条件均不满足）；
丑陋的数组让 Polycarp 心烦意乱，所以他想从数组 a 中删除一些元素，让它变得漂亮。帮助 Polycarp 确定要删除的最少元素数量，以使数组更美观。
输入
第一行包含一个整数 t (1≤t≤10) — 测试用例的数量。然后是 t 个测试用例。
每个测试用例的第一行包含一个整数 n (1≤n≤2?105) — 数组 a 的长度。
每个测试用例的第二行包含 n 个数字 a1,a2,…,an (1≤ai≤2?105) — 数组 a 的元素。
输出
对于每个测试用例输出一个整数——为使数组美观而必须删除的最小元素数。
题解思路
一开始是想的筛每个数在题目中目标数组中含有的因子理论复杂度2.7*1e8.5（有点悬），写挂了。
看了t宝的代码，发现是调和级数，属于是没想到，这种整除的问题除了想因子还得想调和级数来处理。
dp[i]表示以i结尾的能组成的最长的整除序列。
利用调和级数dp[j]来转移之后的值。
时间复杂度Onlogn
AC代码
#include <bits/stdc++.h>
//#include <unordered_map>
//priority_queue
#define PII pair<int,int>
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 200100;
int a[N] ;
int cnt[N] ;
int f[N] ;
void solve()
{
int n ;
cin >> n ;
int ma = 0 ;
for (int i = 1 ; i < N ; i++ )
f[i] = 0 , cnt[i] = 0 ;
for (int i = 1 ; i <= n ; i++ )
cin >> a[i] , ma = max(a[i],ma) ;
sort(a+1,a+1+n) ;
for (int i = 1 ; i <= n ; i++ )
cnt[a[i]]++;
int ans = 0 ;
for (int i = 1 ; i <= ma ; i++ )
{
f[i] += cnt[i] ;
for (int j = i*2 ; j <= ma ; j += i )
{
f[j] = max(f[i],f[j]) ;
}
ans = max(f[i],ans) ;
}
cout << n - ans << "\n" ;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T ;
cin >> T ;
while (T--)
solve() ;
return 0 ;
}
