Concurso de Programación UNMSM-FISI 2011
Problema E: MCDFAC
Descargar problema: UNMSM-FISI 2011 Problema E
import java.io.*;
public class ProblemaE
{
public static void main( String args[] ) throws Exception
{
BufferedReader br = new BufferedReader( new InputStreamReader(
System.in ) );
int numCasos; // Cantidad de casos a analizar
int a, b; // Par de valores a analizar
int mcd; // MCD
int[] exp;
int limite; // Limite hasta donde se buscaran divisores
String[] valores;
numCasos = Integer.parseInt( br.readLine() );
for( int i = 0; i < numCasos; i ++ )
{
// Leemos los valores de entrada
valores = br.readLine().split( " " );
a = Integer.parseInt( valores[ 0 ] );
b = Integer.parseInt( valores[ 1 ] );
mcd = 1;
// Verificamos si el segundo es multiplo de 2
if( b % 2 == 0 )
{
exp = factor( b, 2 );
b = exp[ 0 ];
// Calculamos el menor exponente de 2, en los 2 numeros
mcd = (int)Math.pow( 2, Math.min( exp[ 1 ], maximo( a, 2 ) ) );
}
// Numero maximo que puede ser divisor de 'b'
limite = (int)Math.sqrt( b );
for( int j = 3; j <= limite; j = j + 2 )
{
// Buscamos los siguientes divisores de 'b'
if( b % j == 0 )
{
exp = factor( b, j );
b = exp[ 0 ];
// Calculamos el menor exponente de 'j' en los 2 numeros
mcd *= Math.pow( j, Math.min( exp[ 1 ], maximo( a, j)));
// Calculamos el nuevo limite
limite = (int)Math.sqrt( b );
}
}
// Si el resto es diferente de 1, es un primo, lo añadimos al MCD
if( b != 1 && b <= a )
mcd *= b;
System.out.println( "Caso #" + (i+1) + ": " + mcd );
}
}
// Calcula el exponente de 'divisor' en la descomposicion canonica de 'n'
public static int[] factor( int n, int divisor )
{
int[] exp = { n, 0 };
while( exp[ 0 ] % divisor == 0 )
{
exp[ 1 ] ++;
exp[ 0 ] /= divisor;
}
return exp;
}
// Calcula el exponente de 'divisor' en la descomposicion canonica de n!
public static int maximo( int n, int divisor )
{
int maximo = 0;
while( n >= divisor )
{
n = n/divisor;
maximo += n;
}
return maximo;
}
}
