2. You are given two integers a and b.
Find two integers x and y such that:
1. x divides a.
2. y divides b.
3. x + y divides both a and b.
4. x > 1 and y > 1
If there are multiple valid pairs (x, y), choose the one with the smallest x.
If there are still multiple options, choose the one with the smallest y.
If no such pair exists, print -1.
Input
Two integers a and b
Output
Print two integers x and y — the required pair.
If no valid pair exists, print -1.
Example 1
Input
12 18
Output
3 3
Explanation
• Divisors of 12 are [1, 2, 3, 4, 6, 12].
• Divisors of 18 are [1, 2, 3, 6, 9, 18].
• Pair (3, 3) works because 3 | 12, 3 | 18, and (3 + 3) = 6 divides both 12 and 18.
• This is the lexicographically smallest valid pair.
Example 2
Input
7 11
Output
-1
Explanation
No divisors x of 7 and y of 11 satisfy the condition that x + y divides both 7 and 11.
Constraints :
2 ≤ a, b ≤ 10^6
Time complexity : O(√a + √b + d(a) * d(b))
Space Complexity : O(d(a) + d(b))
d(x) : number of divisors of x
Please Whitelist JSFiddle in your content blocker.
Help keep JSFiddle free for always by one of two ways:
Whitelist JSFiddle in your content blocker (two clicks)
Go PRO and get access to additional PRO features →
Join the 4+ million users, and keep the JSFiddle dream alive.
Ad-free
All ads in the editor and listing pages are turned completely off.
Use pre-released features
You get to try and use features (like the Palette Color Generator) months before everyone else.
Fiddle collections
Sort and categorize your Fiddles into multiple collections.
Private collections and fiddles
You can make as many Private Fiddles, and Private Collections as you wish!
Console
Debug your Fiddle with a minimal built-in JavaScript console.