# PROBLEM LINK:

Division 1

Division 2

Practice

**Author:** Anton Trygub

**Tester:** Alexander Morozov

**Editorialist:** Colin Galen

# DIFFICULTY:

Simple

# PREREQUISITES:

Math, Number Theory, Observations

# PROBLEM:

You have a sequence a_1, a_2, \dots, a_n of integers, where a_i = i. You’re also given a sequence of n integers b_1, b_2, \dots, b_n, where b_i \leq a_i for all i. You may perform some number (possibly zero) of the following operation: choose two indices i, j, and set both a_i and a_j to \gcd(a_i, a_j). Find out if it’s possible to make all a_i = b_i.

# QUICK EXPLANATION:

## Main solution

It’s only possible if for all i, a_i is divisible by b_i, otherwise impossible.

# EXPLANATION:

## Main solution

What’s the scope of values we can set a_i to using the operation? If we want to set a_i to some x, and a_i isn’t divisible by x, then it’s impossible for the GCD of any other number and a_i to be x, as x isn’t even a divisor of a_i. So our first condition is that for all i, a_i must be divisible by b_i, otherwise it’s immediately impossible.

It turns out this is the only condition. The next step in piecing together this solution is the observation that if you select some i, j where a_i is directly divisible by a_j, their GCD is a_j by definition. So after the operation, a_j is unchanged. This is cool because all of the numbers 1 \dots n are present in the array. So if we process a_i before we process any of its divisors, since b_i is assumed to be a divisor of a_i, we can make a_i correct without affecting any other value in the array by just selecting b_i as the other index.

We can “process a_i before we process any of its divisors” simply by going backwards through a, since all divisors of a number are less than or equal to it. So as long as b_i divides a_i for all i, a solution exists.

# TIME COMPLEXITY:

## Main solution

O(n) for reading in the input and checking if all b_i are divisible by a_i.

# SOLUTIONS:

## Setter's Solution

```
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n;
cin>>n;
vector<int> b(n);
for (int i = 0; i<n; i++) cin>>b[i];
for (int i = 0; i<n; i++) if ((i+1)%b[i]) {cout<<"NO"<<endl; return;}
cout<<"YES"<<endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int t; cin>>t;
while (t--) solve();
}
```

## Tester's Solution

```
#include <bits/stdc++.h>
using namespace std;
using nagai = long long;
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
vector<int>b(n);
for(auto&x : b) cin >> x;
bool ok=true;
for(int i=0;i<n;++i)
ok &= (i + 1) % b[i] == 0;
cout << (ok ? "YES" : "NO") << '\n';
}
return 0;
}
```

## Editorialist's Solution

```
#include <bits/stdc++.h>
using namespace std;
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL); cout.tie(NULL);}
typedef long long ll;
void solve(int tc = 0) {
ll n, x;
cin >> n;
bool pos = 1;
for (ll i = 0; i < n; i++) {
cin >> x;
pos &= ((i + 1) % x == 0);
}
cout << (pos ? "YES\n" : "NO\n");
}
int main() {
send help
int tc = 1;
cin >> tc;
for (int t = 0; t < tc; t++) solve(t);
}
```

# Video Editorial(s)

My video: CodeChef September Lunchtime 2020 - All Solutions (Div. 1 + Div. 2) - YouTube

Official video: - YouTube