Min Combinations

help
, ,
1

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
Explanation
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

I know if two number are odd and there modulos is not zero so the result will be 1 and if two number give modulus zero there answer will be the same smalller number and if both are even and do not give modulos zero there answer will be 2… But i just want know how to deal with this range… If gcd of number goes out of range, how can i calculate the answer…

2

The answer of this question is GCD of the two numbers. Please look through the extended euclid’s algorithm and the chinese remainder theorem.

1 Like
3

I totally agree with @anon70990627，this is a simple problem based extended euclid’s algorithm, It means if ax + by = c have a solution of interger, it must be c \ \% \ gcd(a, b) = 0, so the min of c is gcd(a, b).

2 Likes
4

Solution:-------------------

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b)
{
return (a%b == 0)? abs(b) : gcd(b,a%b);
}
bool isPossible(int a, int b, int c)
{
return (c%gcd(a,b) == 0);
}

int main()
{
int t;
cin>>t;
while(t–)
{
int n1,n2;
cin>>n1>>n2;
for(int i=1;i<=1000000;i++)
{
if(isPossible(n1,n2,i))
{
cout<<i;
break;
}
else
continue;
}
}

return 0;
}