# [PKU] P1306: Combinations

### Description

Computing

the exact number of ways that N things can be taken M at a time can be

a great challenge when N and/or M become very large. Challenges are the

stuff of contests. Therefore, you are to make just such a computation

given the following:

GIVEN: 5 <= N <= 100; 5 <= M <= 100; M <= N

Compute the EXACT value of: C = N! / (N-M)!M!

You may assume that the final value of C will fit in a 32-bit

Pascal LongInt or a C long. For the record, the exact value of 100! is:

93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621,

468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253,

697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,000,000,000

the exact number of ways that N things can be taken M at a time can be

a great challenge when N and/or M become very large. Challenges are the

stuff of contests. Therefore, you are to make just such a computation

given the following:

GIVEN: 5 <= N <= 100; 5 <= M <= 100; M <= N

Compute the EXACT value of: C = N! / (N-M)!M!

You may assume that the final value of C will fit in a 32-bit

Pascal LongInt or a C long. For the record, the exact value of 100! is:

93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621,

468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253,

697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,000,000,000

### Input

The

input to this program will be one or more lines each containing zero or

more leading spaces, a value for N, one or more spaces, and a value for

M. The last line of the input file will contain a dummy N, M pair with

both values equal to zero. Your program should terminate when this line

is read.

input to this program will be one or more lines each containing zero or

more leading spaces, a value for N, one or more spaces, and a value for

M. The last line of the input file will contain a dummy N, M pair with

both values equal to zero. Your program should terminate when this line

is read.

### Output

The output from this program should be in the form:

N things taken M at a time is C exactly.

N things taken M at a time is C exactly.

### Sample Input

1 |
100 6<br>20 5<br>18 6<br>0 0 |

### Sample Output

1 |
100 things taken 6 at a time is 1192052400 exactly.<br>20 things taken 5 at a time is 15504 exactly.<br>18 things taken 6 at a time is 18564 exactly. |

### Source

### Solution:

[#M_ more.. | less.. |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
import java.math.BigInteger; import java.util.*; public class P1306 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while(true){ String temp = sc.nextLine(); StringTokenizer st = new StringTokenizer(temp, " "); String sn = st.nextToken(); String sm = st.nextToken(); int n =Integer.parseInt(sn); int m = Integer.parseInt(sm); if(n==0){ break; } BigInteger bn = new BigInteger(sn); BigInteger bm = new BigInteger(sm); BigInteger answer; answer = (factorial(bn).divide(((factorial(bn.subtract(bm)).multiply(factorial(bm)))))); System.out.println(bn+" things taken "+bm+" at a time is "+answer+" exactly."); } } public static BigInteger factorial( BigInteger n ) { if( n.compareTo(new BigInteger("1"))<=0 ) // base case return new BigInteger("1"); else return n.multiply(factorial( n.subtract(new BigInteger("1")))); } } |