Course


Big Integer

Learn to solve big number problems.

Big number problems

Long time ago, 16-bit integer is sufficient: -32,768 to 32,767. When 32-bit machines are getting popular, 32-bit integers become necessary. This data type can hold range from 2,147,483,648 to 2,147,483,647. Any integer with 9 or less digits can be safely computed using this data type. If you somehow must use the 10th digit, be careful of overflow. But man is very greedy, 64-bit integers are created, referred as programmers as long long data type or Int64 data type. It has an awesome range up that can covers 18 digits integers fully, plus the 19th digit partially [-2^63-1 to 2^63-1] ~ 9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. Practically this data type is safe to compute most of standard arithmetic problems, except some problems.

Solve UVa problems related with Big Integer:

  • 485 - Pascal Triangle of Death
  • 495 - Fibonacci Freeze - plus Fibonacci
  • 10007 - Count the Trees - plus Catalan formula
  • 10183 - How Many Fibs - plus Fibonacci
  • 10219 - Find the Ways ! - plus Catalan formula
  • 10220 - I Love Big Numbers ! - plus Catalan formula
  • 10303 - How Many Trees? - plus Catalan formula
  • 10334 - Ray Through Glasses - plus Fibonacci
  • 10519 - !!Really Strange!!
  • 10579 - Fibonacci Numbers - plus Fibonacci

For those who don't know, in C, long long n is read using: scanf("%lld",&n); and unsigned long long n is read using: scanf("%llu",&n); For 64 bit data: typedef unsigned long long int64; int64 test_data=64000000000LL.


10219 - Find the Ways

In how many ways you can destroy k slums out of n slums! Suppose there are 10 slums and you are given the permission of destroying 5 slums, surly you can do it in 252 ways, which is only a 3 digit number, Your task is to find out the digits.

Sample Input

20 5
100 10
200 15

Sample Output

5
14
23

Solution

C++ (GCC 9.2.0)
  • Input