Solução Mini-calculadora

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:


#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:


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");
}
}