Solução por Rogério Júnior
A questão quer que tiremos todos os fatores comuns entre D e Q, ou seja, que dividamos os dois pelo Máximo Divisor Comum (MDC) entre eles. Para encontrar o MDC entre dois números, basta que realizemos o Algoritmo de Euclides. Encontrado o MDC entre D e Q, vamos dividí-los por esse valor e verificar se são menores que o valor de N. Se um dos dois não for, imprimo “IMPOSSIVEL”, se não, imprimo os valores de D e Q respectivamente.
Vale lembrar que essa questão é da OBI de 2008 e o corretor oficial do site a corrige como se números iguais a N fossem possíveis de serem impressos, o que não foi dito na questão. Outra ponto não muito claro, é que N já é o valor máximo que pode ser representado, e não $$2^N$$, mas essa dúvida pode ser tirada já no segundo caso de teste que a questão nos dá, visto que 65 é muito menor que $$2^16$$, mas é maior que 16. Segue o código comentado:
https://gist.github.com/rogerioagjr/0ee00e50200be36a8373
Nosso leitor Roger Benet também fez uma solução correta em Java:
https://gist.github.com/rogerioagjr/1a79124ba6c7bd2afe0b
Deixe um comentário