# PROBLEM LINK:

* Author:* Aryan Agarwal

*Aryan Agarwal*

**Tester:***Srikkanth*

**Editorialist:**# DIFFICULTY:

Cakewalk

# PREREQUISITES:

Arrays

# PROBLEM:

Given a circular array A, and integers X, Y,

starting from position X keep moving to position X + K (coming back to the first point when needed).

Will you ever reach position Y?

# EXPLANATION:

There are only a finite number of cities, after some time, we will visit a city again.

After this point no new city will be visited and we will end up visiting the same cities again and again in a cycle.

We can implement this by keeping a visited array and stop after some position is visited already.

Finally if we visited position Y, answer is “YES”, otherwise “NO”.

This complexity of above method is \mathcal{O}(n) and is more than enough to get 100 pts, however I’d like to describe a more efficient solution, which wasn’t required because we intended this to be a cakewalk problem.

The position after t jumps is (X + kt) \mod n.

We need to find if there exists some integer t such that Y = (X + kt) \mod n

Which implies there is a pair of integers t, l such that X + kt = Y + nl

Rewriting this we get, X-Y = nl - kt

Observing the above equation, we know that rhs is divisible by gcd(n, k) (because this divides both n and k and hence the difference also)

Therefore X-Y should be divisible by gcd(n, k)

We can obtain the numbers t, l using extended euclid algorithm, so the above condition is sufficient.

Therefore the answer is “YES” if (X - Y) is divisible by gcd(n, k) otherwise “NO”.

This solution is \mathcal{O}(\log n)

# TIME COMPLEXITY:

**TIME:** \mathcal{O}(\log n)

**SPACE:** \mathcal{O}(1)

# SOLUTIONS:

## Setter's Solution

```
//created by Whiplash99
import java.io.*;
import java.util.*;
class A
{
private static long _gcd(long a, long b) {return a==0?b:_gcd(b%a,a);}
public static void main(String[] args) throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int i,N;
int T=Integer.parseInt(br.readLine().trim());
StringBuilder sb=new StringBuilder();
while (T-->0)
{
String[] s=br.readLine().split(" ");
N=Integer.parseInt(s[0]);
int K=Integer.parseInt(s[1]);
int X=Integer.parseInt(s[2]);
int Y=Integer.parseInt(s[3]);
boolean[] vis=new boolean[N];
for(i=X;!vis[i];i=(i+K)%N) vis[i]=true;
sb.append(vis[Y]?"YES\n":"NO\n");
}
System.out.println(sb);
}
}
```

## Editorialist's Solution

```
#include<bits/stdc++.h>
using namespace std;
#define LL long long int
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int oo = 1e9 + 5;
const LL ooll = (LL)1e18 + 5;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l, r) uniform_int_distribution<int>(l, r)(rng)
clock_t start = clock();
const int N = 1e5 + 5;
void solve() {
int n, k, x, y;
cin >> n >> k >> x >> y;
assert(1 <= n && n <= 1000);
assert(0 <= x && x <= n-1);
assert(0 <= y && y <= n-1);
assert(0 <= k && k <= 1000);
y = abs(y - x);
if (y % __gcd(n, k) == 0) cout << "YES\n";
else cout << "NO\n";
}
int main() {
FASTIO;
int T = 1;
cin >> T;
assert(1 <= T && T <= 100);
for (int t=1;t<=T;++t) {
solve();
}
cerr << fixed << setprecision(10);
cerr << "Time: " << (clock() - start) / (CLOCKS_PER_SEC) << " secs\n";
return 0;
}
```