Given three positive integer n, x, y. The task is to print Greatest Common Divisor of numbers formed by n repeating x times and number formed by n repeating y times.
0 <= n, x, y <= 1000000000.
Input : n = 123, x = 2, y = 3. Output : 123 Number formed are 123123 and 123123123. Greatest Common Divisor of 123123 and 123123123 is 123. Input : n = 4, x = 4, y = 6. Output : 44
The idea is based on Euclidean algorithm to compute GCD of two number.
Let f(n, x) be a function which gives a number n repeated x times. So, we need to find GCD(f(n, x), f(n, y)).
Let n = 123, x = 3, y = 2.
So, first number A is f(123, 3) = 123123123 and second number B is f(123, 2) = 123123. We know, GCD(A,B) = GCD(A – B, B), using this property we can substract any multiple of B, say B’ from first A as long as B’ is smaller than A.
So, A = 123123123 and B’ can be 123123000. On substracting A will became 123 and B remains same.
Therfore, A = A – B’ = f(n, x – y).
So, GCD(f(n, x), f(n, y)) = GCD(f(n, x – y), f(n, y))
We can conclude following,
GCD(f(n, x), f(n, y)) = f(n, GCD(x, y)).
Below is the implementation based on this approach:
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.