Page Contents
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:
- 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