PRIMESM-Editorial

Setter: Rahul Kumar
Tester: Istvan Nagy, Aryan
Editorialist: Vijay

Easy

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