如题, 使用 AtCoder Library.

void solve(vector<int> &pos) {
	int n;
	cin >> n;
	mf_graph<int> G(4 * n + 2);
	int source = 4 * n, sink = 4 * n + 1;
	vector<int> a(n);

	for (int &x : a)
		cin >> x;

	sort(a.begin(), a.end());

	for (int i = 0; i < n; i++)
		pos[a[i]] = i, ae(G, i, i + n * 3, 1);

	for (int i = 0; i < n * 2; i++)
		ae(G, source, i, 1), ae(G, i + n * 2, sink, 1);

	if (n > 1000) {
		for (int i = 1; i <= a.back(); i++)
			if (pos[i] >= 0)
				for (int j = i * 2; j <= a.back(); j += i)
					if (pos[j] >= 0)
						ae(G, pos[i], pos[j] + n * 2, 1),
						ae(G, pos[i] + n, pos[j] + n * 3, 1);
	} else
		for (int i = 0; i < n; i++)
			for (int j = i + 1; j < n; j++)
				if (a[j] % a[i] == 0)
					ae(G, i, j + n * 2, 1),
					ae(G, i + n, j + n * 3, 1);


	cout << (G.flow(source, sink) - n) << endl;

	for (int i = 0; i < n; i++)
		pos[a[i]] = -1;
}

signed main() {
	vector<int> pos(50001, -1);

	int T;
	cin >> T;

	while (T --)
		solve(pos);
}

前面是 AtCoder Library, mf_graph 为实现最大流功能的函数.