Min Combinations
Problem Description
Alexander The great, while roaming the stretch of Turkey, came across a wise man.He asked the wise man, "Who is the greatest conqueror of all?". The wise man replied, "A person with great strength and
intelligence. Whosoever can solve my puzzle will go on to become the greatest!". The puzzle is as follows; Given two integers
'n1' and 'n2', select two integers 'a' and 'b', such as to solve the equation (n1 * a + n2 * b = x). But there is a catch, 'x' is the smallest
positive integer which satisfies the equation. Can you help Alexander become the greatest?
Constraints
1 <= T <= 1000-10^7 <= a, b <= 10^7
0 <= n1, n2 <= 10^7
Input Format
The first line contains the number of Test cases T.Next T lines contains two space-separated integers, n1 and n2.
Output
Print the value of x.Test Case
Example 1
Input
1
34818 45632
Output
2
Explanation
Given n1 = 34818 and n2 = 45632, if we choose a = 3553 and b = -2711, we get
=> n1 * a + n2 * b = x
=> 34818 * 3553 + 45632 * (-2711)
=> 2
Note: No other value of a and b, within the range, will give smaller value than 2.
Program
#include <stdio.h>
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
int main()
{
int a,b,t,i;
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%d %d",&a,&b);
printf("%d\n", gcd(a, b));
}
return 0;
}
You can also run it on an online IDE: https://ide.geeksforgeeks.org/OshEmrNKoJ
Your feedback are always welcome! If you have any doubt you can contact me or leave a comment!! Cheers!!!
Related Links:
