Page Contents
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:
- Dazzling AXNODR Challenge AXNODR Codechef Solution
- Dazzling GCD Pair NOTUNIT Solution
- The Cooler Dilemma 2 WATERCOOLER2 Solution
- The Cooler Dilemma 1 WATERCOOLER1 Solution
- Ezio and Guards MANIPULATE Codechef Solution
- Pairwise Xors XORABC Codechef Solution
- Prime Sum PRIMESM Codechef Solution