Dazzling GCD Pair NOTUNIT Solution
Dazzler has a task for you. Given two positive integers A and B, find two positive integers i and j such that:
- gcd(i,j)>1;
- A≤i<j≤B;
- The value (i+j) is minimum possible.
If there are multiple solutions, you may print any of them. If no such pair exists, print −1.
Input Format
- First line will contain T, number of test cases. Then the test cases follow.
- Each test case contains of a single line of input, two integers A and B.
Output Format
For each test case, output in a single line two space-separated integers i and j satisfying all the conditions. If no such pair exists, print −1.
Constraints
- 1≤T≤105
- 1≤A<B≤109
Sample Input 1
2
2 3
2 10
Sample Output 1
-1
2 4
Explanation
- Test case 1: There exists no pair satisfying all the conditions.
- Test case 2: A valid pair satisfying all the conditions is (i,j)=(2,4). The value gcd(2,4)=2>1. The value (i+j)=6.
It can be proven that no such pair exists that satisfies all the conditions and has sum less than 6.
SOLUTION
Program: Dazzling GCD Pair NOTUNIT Solution in Python
for _ in range (int(input())):
x,y=map(int,input().split())
if (x%2==0):
if(y-x>=2):
print(x,x+2)
else:
print(-1)
else:
if(y-x >=3):
if(x%3==0):
print(x,x+3)
else:
print(x+1,x+3)
else:
print(-1)
Program: Dazzling GCD Pair NOTUNIT Solution in C++
#include <iostream>
using namespace std;
int main() {
int t,a,b;
cin>>t;
while(t--){
cin>>a>>b;
if(a%2==0){
if(b>=a+2) cout<<a<<" "<<a+2;
else cout<<-1;
}
else{
if(b<a+3) cout<<-1;
else if(a%3==0) cout<<a<<" "<<a+3;
else cout<<a+1<<" "<<a+3;
}
cout<<"\n";
}
return 0;
}
Program: Dazzling GCD Pair NOTUNIT Solution in Java
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner s=new Scanner(System.in);
int n=s.nextInt();
while(n-->0){
int a=s.nextInt();
int b=s.nextInt();
if(Math.abs(a-b)<2){
System.out.println(-1);
}
else if(a%2==0){
System.out.println(a+" "+(a+2));
}
else{
if(Math.abs(a-b)==2){
System.out.println(-1);
}
else if(a%3==0){
System.out.println(a+" "+(a+3));
}
else{
System.out.println((a+1)+" "+(a+3));
}
}
}
}
}
Related: