# PROBLEM LINK

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Rahul Kumar

Tester: Istvan Nagy, Aryan

Editorialist: Vijay

# DIFFICULTY:

Easy

# PREREQUISITES:

None

# PROBLEM:

Given two integers A and B.

- Let P denote a sequence of N prime numbers such that the sum of the sequence is A.
- Let Q denote a sequence of M prime numbers such that the sum of the sequence is B.

Let X denote the **maximum absolute difference** between P_i and Q_j among all valid pairs (i,j) such that (1 \leq i \leq N) and (1 \leq j \leq M).

Find the **minimum** possible value of X over all possible sequences P and Q.

More formally, for all possible sequences P and Q, find the **minimum** value of \texttt{max}(|P_i - Q_j|), where (1 \leq i \leq N) and (1 \leq j \leq M).

Print -1 if any one of the sequences cannot be formed.

Note that, |X| denotes the absolute value of a number X. For example, |-4| = 4 and |7| = 7.

# EXPLANATION:

## What is the minimum sum of a valid sequence ?

We know that the smallest prime number is equal to 2. So, the minimum sum of the sequence is at least equal to 2. Thus, if we have A or B equal to 1, we cannot form a sequence.

## Can we always form a valid sequence in case both A and B are greater than 1?

Let’s suppose that sum of the sequence is *X*>1.

*Case 1:*

if *X* is even, then we can always form the sequence using only prime number 2.

*Case 2:*

if *X* is odd, then we can use a prime number 3, then *X-3* will be an even number. So we can form the rest of the sequence as in an even case.

So, when both A and B are even then max(∣P_i−Q_j∣) will be definitely 0 otherwise, it can be equal to at most 1 as we are using 2 and 3 only.

## How can we improve further ?

Now we know that answer cannot be greater than 1. So, we should check if we can make the answer equal to 0. This implies that we have to use a single prime number to evaluate max(∣P_i−Q_j∣) equal to 0 for forming both sequences.

Suppose this prime number equals K. Now we are claiming that K can be used N number of times to form the sum of sequence equal to A. Also, K can be used M number of times to form the sum of sequence equal to B. This implies that N \cdot K=A and M \cdot K=B, which further means that K divides both A and B. So, K can be either gcd of A and B or some factor of their gcd.

Thus if gcd(A, B)>1, we can find such K to obtain the answer as 0.

# TIME COMPLEXITY:

O(log(min(A,B)) for each test case.

# SOLUTION:

## Editorialist's Solution

```
#include <bits/stdc++.h>
using namespace std;
#define nline '\n'
void solve()
{
long long a,b;
cin>>a>>b;
if(min(a,b)<=1){
cout<<-1<<online;
return;
}
if(__gcd(a,b)>1)cout<<0<<online;
else cout<<1<<nline;
}
int main()
{
int t=1;
cin >> t;
while (t--)
{
solve();
}
}
```