toj_2901_gen.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 MAX 3010

FILE *fOut = fopen( "toj_2901_prime.txt" , "w"  );

void setPrime( int num[] )
{
  int i , j;
  memset( num , 0  , MAX * sizeof( int ) );
  for ( i = 2; i < MAX; i++ )
    {
      if ( num[ i ] == 0 )
	{
	  for ( j = i * 2; j < MAX; j+= i )
	    num[ j ] = -1;
	}
    }
}  

int main()
{
  int i , j;
  int num[ MAX ];
  setPrime( num );
  num[ 0 ] = 1;
  num[ 1 ] = 1;
  fprintf( fOut , "{1" );
  for ( i = 1;i < MAX; i++ )
    {
      if ( num[ i ] == 0 )
	fprintf( fOut , ",%d" , num[ i ] );
      else
	fprintf( fOut, ",SL" );
    }
  fprintf( fOut , "}" );
  return 0;
}