Əsas Xarakter (Həll təhlili)

Həll

Fakt 1 : Həmişə $(1,n)$ istifadə etmək optimaldır, maksimum cəmi təmin etmək şərti ilə.

Hallara diqqətlə baxaq, $n$ tək olduğu halda $(1,n)$ istifadə edə bilərik, çünki $n$ təkdir və tək ədədin $0$ ilə bitməsi mümkün deyil, çünki bir ədəd $10$ ilə bitirsə, $2$ və $5$-ə bölünməlidir, buna görə də tək $n$ üçün $(1,n)$ istifadə edirik.

\gcd(n,10)=2 olduğu halda, bu halda sonuncu rəqəm 2,4,6,8-dən biri olur, amma $0$ deyil, buna görə də $(1,n)$ cavab olaraq istifadə edə bilərik.

\gcd(n,10)=5 olduğu halda, bu halda sonuncu rəqəm $5$ olur, buna görə də $(1,n)$ istifadə edə bilərik.

İndi son hal \gcd(n,10)=10 olduğu halda, bu halda $x$ və $y$-də $0$ bitməməsi üçün $2$-nin və $5$-in qüvvələrini ayırmaq optimaldır, bu, $n$-i bölən $5$-in maksimum qüvvəsini və $2$-nin maksimum qüvvəsini hesablamaqla \mathcal{O}(\log_5(n)), \mathcal{O}(\log_2(n)) ilə həyata keçirilə bilər.

p_2,p_5 $n$-i bölən $2$ və $5$-in maksimum qüvvələri olsun, o zaman birinci ədəd olaraq \min(2^{p_2},5^{p_5}) istifadə etmək optimaldır və ikinci ədəd olaraq \frac{n}{\max(2^{p_2},5^{p_5})} istifadə etmək optimaldır.

Komplekslik \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()