题解 | #E 牛牛的约数#

牛客小白月赛120 E 牛牛的约数

把所有数字去重，记录下每个数字对应的任一原坐标。

把数字排序，从小到大确定每个数字对应的答案。

对所有已经遍历过的数字构建若干条非因数（即不能整除）链，每个数字指向小于他的最大非因数，如果没有则置为 。

确定每个数字 的答案时，沿非因数链不断回溯，知道找到一个数 使得 或者 。

void solve()
{
	int n;
	cin >> n;
	vector<int64_t> as(n + 1);
	map<int64_t, int> m;
	for (int i = 1; i <= n; ++i)
	{
		cin >> as[i];
		m[as[i]] = i;
	}
	// v : [a, index[a] in as]
	vector<pair<int64_t, int>> v(m.begin(), m.end());
	// indexs : [a, index[a] in v]
	map<int64_t, int> indexs;
	for (int i = 0; i < v.size(); ++i)
	{
		indexs[v[i].first] = i;
	}
	// dp : index in v -> index[ans[a]] in v
	vector<int> dp(v.size(), -1);
	for (int i = 1; i < dp.size(); ++i)
	{
		int j = i - 1;
		while (v[i].first % v[j].first == 0 && dp[j] != -1)
		{
			j = dp[j];
		}
		if (v[i].first % v[j].first)
			dp[i] = j;
	}
	vector<int> ans(n + 1);
	for (int i = 1; i <= n; ++i)
	{
		ans[i] = dp[indexs[as[i]]] == -1 ? -1 :v[dp[indexs[as[i]]]].second;
	}
	for (int i = 1; i <= n; ++i)
	{
		cout << ans[i] << " ";
	}
	cout << endl;
}