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.
-10^7 <= a, b <= 10^7
0 <= n1, n2 <= 10^7
how it can be solved
i assume that it is a gcd problem like gcd(n1,n2)=x so it give correct answer for all test cases?
I think that’s correct, Can you provide the link to the problem?
i dont have a link because it is codevita problem
i am providing test case for this problem
eg
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
ohh this means that gcd is a correct answer for this
Learn Extended Euclidean Theorem Then Learn Chinese Remainder and the Diophantine equation
For Equation to be solvable It is compulsion That x should be divisible by The GCD of(n1,n2) It is rule. And X should be minimum as given in condition x must be GCD(n1,n2) so it is always be divisble.
Eg.170 x - 455 y = 625;
First we check whether it is solvable or not. As it is solvable because GCD of(170,455) divides 625 that is 5. GCD=5 NOW;
By assumption or hit trial we find putting x=1 and y=-1 satisfies this equation Now let x1=1 and y1=-1;
Now solutions of this equations are x = (x1 - (b/GCD)*T)
AND Y=(y1 +(a/GCD)*T) are yours solution;;;;Hope I am able to clear;
Where T is integer!! Thanks For Asking!!!1
do u know diophantine equations?
it is relatively easy when you know that
Simply use Bezout’s lemma.