toj_2901_ac.cpp

Tianjin University Online Judge 的80多道题目 .

/*2901.   Very easy 
--------------------------------------------------------------------------------
Time Limit: 2.0 Seconds   Memory Limit: 65536K
Total Runs: 131   Accepted Runs: 46
Case Time Limit: 1.0 Seconds

--------------------------------------------------------------------------------



This is very simple problem, you only have to display the prime factorization of nCr. For example: 10C5=252=2 * 2 * 3 * 3 * 7

Input:

This is multiple test case problem. Input is terminated by end of file.

Each line contains one test case and it contains two positive numbers n and r.

(2 ≤ n ≤ 3000 && 1 ≤ r ≤ n-1)

Output: 

Out put is the prime factorization of nCr. The output format is below:

nCr = n1 * n2 * n3 * .......... * nth

Sample Input:

10 5
20 10
8 4
30 25

Sample Output:

10C5 = 2 * 2 * 3 * 3 * 7
20C10 = 2 * 2 * 11 * 13 * 17 * 19
8C4 = 2 * 5 * 7
30C25 = 2 * 3 * 3 * 3 * 7 * 13 * 29



Problem Setter: MD. SHAKIL AHMED. (CUET AGRODUT)



Source: New Year Challenge Contest*/
#include<cstdio>
#include<cstring>
#define MAXLEN 3010
int factResult[ MAXLEN ] , n , r ;

void findFact( int num , int const &addition )
{
    int static aFact[ 30 ][ 2 ] , nOfAFact;
    int static i ;
    memset( aFact , 0 , sizeof( aFact ) );
    
    for( nOfAFact = 0  , i = 2; i <= num; i++ ){
        if( num % i == 0 ){
            aFact[ nOfAFact ][ 0 ] = i;
            while ( num % i == 0 ){
                num /= i;
                aFact[ nOfAFact ][ 1 ]++;
            }
            nOfAFact++;
        }
    }
    for(  i = 0; i < nOfAFact; i++ ){
        factResult[ aFact[ i ][ 0 ] ] += addition * aFact[ i ][ 1 ];
    }
}
        
int main()
{
    int i , j , aFact[ 30 ] , nOfAFact;
    bool flagFirst;
    
    while ( scanf( "%d%d"  , &n , &r ) != EOF && n && r ){
        printf( "%dC%d =" , n , r );
        
        if( r > n / 2 ) r = n - r;
        memset( factResult , 0 , sizeof( factResult ) );
        
        for( i = 1; i <= r; i++ ){
            findFact( i , -1 );
            findFact( n - r + i , 1 );
        }
        flagFirst = true;
        
        for( i = 2; i <= n; i++ ){
       //      printf( "factResult[ %d ] = %d\n" , i , factResult[ i ] );
            if ( factResult[ i ] != 0  ){
                if( flagFirst ){
                    flagFirst = false;
                    printf( " %d" , i );
                    for( j = 0;  j < factResult[ i ] - 1; j++ )
                        printf( " * %d" , i );
                    }
                
                else{
                    for( j = 0; j < factResult[ i ]; j++ )
                        printf( " * %d" , i );
                }
        }
        }
        printf( "\n" );
    }
    return 0;
}