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 
, 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 
, mas é maior que 16. Segue o código comentado:
This file contains 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 <cstdio> | |
| int n, d, q, x, y; | |
| int main(){ | |
| scanf("%d %d %d", &n, &d, &q); // leio os valores de n, d, e q | |
| x=d; y=q; // faço as auxiliares receberem, inicialmente, os valores de d e q | |
| // garanto que y é o menor | |
| if(x<y){ | |
| int tmp=x; | |
| y=y%x; | |
| x=tmp; | |
| } | |
| // algoritmo de Euclides para encontrar o MDC | |
| while(y!=0){ // enquanto o menor for diferente de 0 | |
| // faço o mdc entre o menor e o resto que o maior deixa na divião pelo menor | |
| if(x<y){ | |
| int tmp=x; | |
| y=y%x; | |
| x=tmp; | |
| } | |
| else{ | |
| int tmp=y; | |
| y=x%y; | |
| x=tmp; | |
| } | |
| } | |
| // ao fim do algoritmo, x será o MDC | |
| d/=x; q/=x; // divido os dois números pelo MDC | |
| if(d<n && q<n) printf("%d %d\n", d, q); // se os números não sperarem n, os imprimo | |
| else printf("IMPOSSIVEL\n"); // se não, imprimo impossível | |
| return 0; | |
| } |
Nosso leitor Roger Benet também fez uma solução correta em Java:
This file contains 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
| import java.util.Scanner; | |
| public class solucao { | |
| public static int mdc(int a,int b){ | |
| int r; | |
| while(true){ | |
| r = a % b; | |
| if(r == 0)break; | |
| a = b; | |
| b = r; | |
| } | |
| return b; | |
| } | |
| public static void main(String[] args){ | |
| Scanner in = new Scanner(System.in); | |
| int n,a,b; | |
| n = in.nextInt(); | |
| a = in.nextInt(); | |
| b = in.nextInt(); | |
| int r = mdc(a,b); | |
| a /= r; | |
| b /= r; | |
| if(n > a && n > b){ | |
| System.out.printf("%d %d\n",a,b); | |
| } | |
| else System.out.println("IMPOSSIVEL\n"); | |
| } | |
| } |