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;
}