Prime Sum PRIMESM Codechef Solution
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 Pi and Qj among all valid pairs (i,j) such that (1≤i≤N) and (1≤j≤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 max(|Pi−Qj|), where (1≤i≤N) and (1≤j≤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.
Input Format
First line will contain T, the number of test cases. Then the test cases follow.
Each test case contains two integers A and B.
Output Format
For each test case, find the minimum possible value of the maximum absolute difference between Pi and Qj for (1≤i≤N) and (1≤j≤M). If any of the sequences can not be formed, print −1 instead.
Constraints
- 1≤T≤105
- 1≤A≤1018
- 1≤B≤1018
Sample Input 1
2
3 6
3 2
Sample Output 1
0
1
Explanation
- Test case 1: Let P={3} and Q={3,3}.
The maximum absolute difference is 0. It can be shown that the maximum absolute difference can not be less than 0. - Test case 2: The only possible sequences are P={3} and Q={2}.
The maximum absolute difference is 1. It can be shown that the maximum absolute difference can not be less than 1.
SOLUTION
Program: Prime Sum PRIMESM Codechef Solution in Python
def gcd(a,b):
if(b==0):
return a
else:
return gcd(b,a%b)
for _ in range(int(input())):
a,b = map(int,input().split(" "))
if a==1 or b==1:
print(-1)
else:
t = gcd(a,b)
if t != 1:
print(0)
else:
print(1)Program: Prime Sum PRIMESM Codechef Solution in C++
#include<bits/stdc++.h>
using namespace std;
#define f for(ll i=0;i<n;i++)
typedef long long ll;
int main(){
ll t;
cin>>t;
while(t--){
ll x,y;
cin>>x>>y;
if(x==1 || y==1)
cout<<-1<<endl;
else if(__gcd(x,y)!=1)
cout<<0<<endl;
else
cout<<1<<endl;
}
}Program: Prime Sum PRIMESM Codechef Solution in Java
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
static long gcd(long a, long b){
if (b == 0) return a;
return gcd(b, a%b);
}
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0){
long a = sc.nextLong();
long b = sc.nextLong();
if (a==1 || b==1){
System.out.println(-1);
}
else if (gcd(a,b)==1){
System.out.println(1);
}
else
System.out.println(0);
}
}
}Related:
