toj_2901.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
#define MAXSTRLEN 1000000
#define SL -3000

int num[ MAX ] ={SL,SL,0,0,SL,0,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,SL,0,SL,0,SL,SL,SL,SL,SL,SL,SL,SL};
void primeFact( int aNum , int const addition )
{
  int static i;
  for ( i = 2; i <= aNum; i++ )
    {
      if ( num[ i ] != SL )
	{
	  while ( aNum % i == 0 )
	    {
	      num[ i ] += addition;
	      aNum /= i;
	    }
	}
    }
}

void printfResult( int const n , int const r , int const primeFact[] )
{
  int static i , len;
  //  char static result[ MAXSTRLEN ] , addition[ 10 ];
  bool static flagFirst;
  printf(  "%dC%d = " , n , r );
  for ( flagFirst = true , len = 0 , i = 2; i < n; i++ )
    {
      while ( num[ i ]  > 0 )
	{
	  if ( flagFirst )
	    {
	      printf( "%d" , i );
	      flagFirst = false;
	    }
	  else
	    printf( " * %d" , i );
	  num[ i ]--;
	}
    }
  printf( "\n" );
}	  
	  
int main()
{
  int n , r , i , j , k , up , down;
  while (  scanf( "%d%d" , &n , &r ) != EOF )
    {
      if ( r > n / 2 ) r = n - r;
      for ( i = r; i > 0; i-- )
	{
	  primeFact( n + 1 - i , 1);	  
	  primeFact( i , -1 );
	}
      printfResult( n , r , num );
    }
  return 0;
}