Solução por Leonardo Paes
Uma observação importante é que 6=2∗3. Isso significa que o número de 3 que dividem n não muda, ou seja, é invariável. A única coisa que pode mudar é o numero de 2, pois podemos multiplicar o número por 2.
Então, para resolvermos o problema, basta contarmos a quantidade de vezes que podemos dividir n por 2 e n por 3. Se a quantidade de 3 for maior ou igual a quantidade de 2, basta multiplicarmos o número por 2 nessa quantidade de vezes e depois dividirmos o número resultante por 6 até ele virar 1. Caso contrário, não conseguimos aumentar o número de 3, portanto é impossível chegarmos a 1, nesse caso imprimimos −1.
Código de exemplo:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| int main(){ | |
| ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); | |
| int t; | |
| cin >> t; | |
| while(t--){ | |
| int n, qtd2 = 0, qtd3 = 0; | |
| cin >> n; | |
| while(n%2 == 0){ | |
| n /= 2; | |
| qtd2++; | |
| } | |
| while(n%3 == 0){ | |
| n /= 3; | |
| qtd3++; | |
| } | |
| if(n!=1 or qtd2>qtd3) cout << -1 << "\n"; | |
| else{ | |
| cout << qtd3-qtd2 + qtd3 << "\n"; | |
| } | |
| } | |
| return 0; | |
| } |
by