CF1794B Not Dividing题解

如果 \(a_i\) 可以整除 \(a_{i - 1}\)，只要在 \(a_i\) 上 \(+1\) 即可，这样 \(a_i \bmod a_{i - 1} = 1\) 就满足题目要求了，如果这样算来最多进行 \(n\) 次操作。

但同时要注意 \(a_{i - 1} = 1\) 的情况。如果 \(a_{i - 1}\) 为 \(1\)，那么怎么 \(+1\) 都是 \(a_i \bmod a_{i - 1} = 0\) 的。

所以如果当前数字处理完了以后为 \(1\) ，一定要 \(+1\) 变为 \(2\)，如此算来最多会进行 \(2n\) 个操作，与题目相符，可以 AC。

/*******************************
| Author:  SunnyYuan
| Problem: B. Not Dividing
| Contest: Codeforces Round 856 (Div. 2)
| URL:     https://codeforces.com/contest/1794/problem/B
| When:    2023-03-06 08:30:31
| 
| Memory:  256 MB
| Time:    2000 ms
*******************************/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (auto& x : a) cin >> x;
	if (a[0] == 1) a[0]++;
	for (int i = 1; i < a.size(); i++) {
		if (a[i] == 1) a[i]++;
		if (a[i] % a[i - 1] == 0) {
			a[i]++;
		}
	}
	for (auto& x : a) cout << x << ' ';
	cout << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T;
	cin >> T;
	while (T--) solve();
	return 0;
}