Головний герой (Розбір)

Рішення

Факт 1 : Завжди оптимально використовувати $(1,n)$ згідно з умовою максимального суми.

Давайте уважно розглянемо випадки, розглянемо випадок, коли $n$ непарне, ми можемо використовувати $(1,n)$, оскільки $n$ непарне і неможливо, щоб непарне закінчувалося на $0$, оскільки число, що закінчується на $10$, повинно ділитися на $2$ і $5$, отже, для непарного $n$ ми використовуємо $(1,n)$.

Розглянемо випадок, коли \gcd(n,10)=2, у цьому випадку остання цифра може бути 2,4,6,8, але не $0$, отже, ми можемо використовувати $(1,n)$ як відповідь.

Для випадку, коли \gcd(n,10)=5, у цьому випадку остання цифра $5$, отже, ми можемо використовувати $(1,n)$.

Тепер для останнього випадку \gcd(n,10)=10, у цьому випадку оптимально розділити степені $2$ і степені $5$, щоб у жодному з $x$ і $y$ не було закінчення $0$, це можна зробити, обчисливши максимальний ступінь $5$, що ділить $n$, і максимальний ступінь $2$, що ділить $n$ за \mathcal{O}(\log_5(n)), \mathcal{O}(\log_2(n)) відповідно.

Нехай p_2,p_5 - максимальні степені $2$ і $5$, що ділять $n$, тоді оптимально використовувати \min(2^{p_2},5^{p_5}) як перше число і \frac{n}{\max(2^{p_2},5^{p_5})} як друге число.

Складність \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()