El Personaje Principal (Editorial)

Solución

Hecho 1 : Siempre es óptimo usar $(1,n)$ dado la condición de suma máxima.

Veamos los casos con cuidado. Consideremos el caso donde $n$ es impar, podemos usar $(1,n)$ porque $n$ es impar y es imposible que un impar termine en $0$, ya que un número que termina en $10$ debe ser divisible por $2$ y $5$, por lo tanto, para $n$ impar usamos $(1,n)$.

Veamos el caso donde \gcd(n,10)=2, en este caso el dígito final es uno de 2,4,6,8 pero no $0$, por lo que podemos usar $(1,n)$ como respuesta.

Para el caso donde \gcd(n,10)=5, en este caso el dígito final es $5$, por lo que podemos usar $(1,n)$.

Ahora para el último caso \gcd(n,10)=10, en este caso es óptimo separar las potencias de $2$ y las potencias de $5$ para que no tengamos un $0$ final en ninguno de $x$ y $y$, esto se puede hacer calculando la máxima potencia de $5$ que divide $n$ y la máxima potencia de $2$ que divide $n$ en \mathcal{O}(\log_5(n)), \mathcal{O}(\log_2(n)) respectivamente.

Sea p_2,p_5 la máxima potencia de $2$ y $5$ respectivamente que divide $n$, entonces es óptimo usar \min(2^{p_2},5^{p_5}) como el primer número y \frac{n}{\max(2^{p_2},5^{p_5})} como el segundo número.

Complejidad \mathcal{O}(t \cdot \log(n)).

from math import *

def solve():
    n=int(input())
    if(gcd(n,10)!=10):
        print(1,n)
    else:
        p2,p5=1,1
        while(n%2==0):
            p2*=2
            n//=2
        while(n%5==0):
            p5*=5
            n//=5
        if(p2>p5):
            print(p5,n*p2)
        else:
            print(p2,n*p5)
    

for _ in range(int(input())):
    solve()