The Main Character (Çözgüdiň düşündirişi)

Solution

Fact 1 : It's always optimal to use $(1,n)$ as of the condition of maximum sum.

Let's look at cases carefully , Let's look at the case where $n$ is odd , we can use $(1,n)$ because $n$ is odd and it's impossible for odd to end with $0$ , since a number ends with $10$ should be divisible by $2$ and $5$ , thus for odd $n$ we use $(1,n)$.

Let's look at case where \gcd(n,10)=2 , in this case ending digit is either of 2,4,6,8 but not $0$ thus we can use $(1,n)$ as an answer.

For the case where \gcd(n,10)=5 , in this case the ending digit is $5$ thus we can use $(1,n)$.

Now for the last case \gcd(n,10)=10 , in this case it's optimal to separate powers of $2$ and powers of $5$ so that we don't have ending $0$ in either of $x$ and $y$ , this can be done by computing max power of $5$ dividing $n$ and max power of $2$ dividing $n$ in \mathcal{O}(\log_5(n)) , \mathcal{O}(\log_2(n)) respectively.

let p_2,p_5 be max power of $2$ and $5$ respectively dividing $n$ then it's optimal to use \min(2^{p_2},5^{p_5}) as the first number and \frac{n}{\max(2^{p_2},5^{p_5})} as the second number.

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