1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define FL(a, b, c) for(int a = (b), a##end = (c); a <= a##end; a++)
#define FR(a, b, c) for(int a = (b), a##end = (c); a >= a##end; a--)
#define lowbit(x) ((x) & -(x))
#define eb emplace_back
constexpr int N = 5e5 + 10;
int tot = 1, head[N], dis[N], a[N], s, t, ans, now[N];
struct edge{
int v, nxt, w;
}e[6000000];
int n;
#define id(x, i, j) (x + i * 2 * n + j * n)
void add(int u, int v){
e[++tot] = {v, head[u], 1}, head[u] = tot;
e[++tot] = {u, head[v], 0}, head[v] = tot;
}
void Add(int u, int v){
add(id(u, 0, 0), id(v, 0, 1));
add(id(u, 0, 0), id(v, 1, 1));
add(id(u, 1, 0), id(v, 1, 1));
}
bool bfs(){
queue<int>q;
FL(i, s, t)dis[i] = 0;
dis[s] = 1, q.emplace(s);
while(!q.empty()){
for(int x = q.front(), i = (now[x] = head[x]), v; i; i = e[i].nxt)
if(e[i].w && !dis[v = e[i].v])dis[v] = dis[x] + 1, q.emplace(v);
q.pop();
}
return dis[t];
}
int dfs(int x, int last){
if(x == t)return last;
int res = last, k;
for(int i = now[x], v; i && res; i = e[i].nxt)
if(e[now[x] = i].w && dis[v = e[i].v] == dis[x] + 1)
if(k = dfs(v, min(res, e[i].w)))e[i].w -= k, res -= k, e[i ^ 1].w += k;
else dis[v] = 0;
return last - res;
}
void solve(){
cin >> n;
memset(dis, 0, (sizeof*dis) * 100000);
tot = 1, ans = s = 0, t = n * 4 + 1;
FL(i, s, t)head[i] = 0;
FL(i, 1, n)cin >> a[i], dis[a[i]] = i;
FL(i, 1, n){
add(id(i, 0, 0), id(i, 1, 1));
add(s, id(i, 0, 0)), add(s, id(i, 1, 0));
add(id(i, 0, 1), t), add(id(i, 1, 1), t);
}
FL(i, 1, 5e4)if(dis[i])FL(j, 2, (int)(5e4) / i)if(dis[j * i])Add(dis[j * i], dis[i]);
while(bfs())ans += dfs(s, 1e9);
cout << ans - n << endl;
}
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while(t--)solve();
return 0;
}
|
