PRIMESM-Editorial

editorial
, , ,
1

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