Problema E: MCDFAC UNMSM-FISI 2011

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