Le Personnage Principal (Corrigé)

Solution

Fait 1 : Il est toujours optimal d'utiliser $(1,n)$ en raison de la condition de somme maximale.

Examinons les cas attentivement. Considérons le cas où $n$ est impair, nous pouvons utiliser $(1,n)$ car $n$ est impair et il est impossible qu'un impair se termine par $0$, puisque un nombre se terminant par $10$ doit être divisible par $2$ et $5$, donc pour un $n$ impair, nous utilisons $(1,n)$.

Considérons le cas où \gcd(n,10)=2, dans ce cas, le chiffre de fin est soit 2,4,6,8 mais pas $0$, donc nous pouvons utiliser $(1,n)$ comme réponse.

Pour le cas où \gcd(n,10)=5, dans ce cas, le chiffre de fin est $5$, donc nous pouvons utiliser $(1,n)$.

Maintenant, pour le dernier cas \gcd(n,10)=10, dans ce cas, il est optimal de séparer les puissances de $2$ et les puissances de $5$ afin de ne pas avoir de $0$ à la fin de $x$ et $y$, cela peut être fait en calculant la puissance maximale de $5$ divisant $n$ et la puissance maximale de $2$ divisant $n$ en \mathcal{O}(\log_5(n)), \mathcal{O}(\log_2(n)) respectivement.

Soit p_2,p_5 la puissance maximale de $2$ et $5$ respectivement divisant $n$, alors il est optimal d'utiliser \min(2^{p_2},5^{p_5}) comme premier nombre et \frac{n}{\max(2^{p_2},5^{p_5})} comme deuxième nombre.

Complexité \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()