Please be easy!#12361

Please be easy! (Editorial)

Problem Author:	Aritro Sarkar
textbfPrepared by:	Hasan Saleh (MathModel)
textbfEdited by:	Hasan Saleh (MathModel)

Solution

The solution can be claimed by observing the pattern for $(a, b, k \leq 50)$ (a,b,k \le 50) or similar bounds , we can verify that the answer is exactly $\frac{a}{b}$ \displaystyle \frac{a}{b} and actually $k$ doesn't matter.

Proof :

By Algebraic Representation : Since $a$ and $b$ both have $L$ digits, repeating a number $x$ for $k$ times can be expressed as a geometric series. Specifically:

f (x, k) = x \cdot (1 + 1 0^{L} + 1 0^{2 L} + \dots + 1 0^{(k - 1) L})

f(x, k) = x \cdot (1 + 10^L + 10^{2L} + \dots + 10^{(k-1)L})

thus

\frac{f ( a , k )}{f ( b , k )} = \frac{a \cdot ( 1 + 1 0 ^{L} + 1 0 ^{2 L} + \dots + 1 0 ^{(k - 1) L} )}{b \cdot ( 1 + 1 0 ^{L} + 1 0 ^{2 L} + \dots + 1 0 ^{(k - 1) L} )} = \frac{a}{b}

\frac{f(a,k)}{f(b,k)}=\frac{a \cdot (1 + 10^L + 10^{2L} + \dots + 10^{(k-1)L})}{b \cdot (1 + 10^L + 10^{2L} + \dots + 10^{(k-1)L})}=\frac{a}{b}

thus we divide both $a, b$ by their greatest common divisor to get the irreducible fraction.

Complexity $O (t \cdot lo g (1 0^{15})$ O(t \cdot \log(10^{15}) which is at most $O (5000)$ operations under the current constraints.

from math import gcd
def solve():
    a,b,k=map(int,input().split())
    print(a//gcd(a,b),b//gcd(a,b))
for _ in range(int(input())):
    solve()