ECOO '18 R2 P3 - Factorial

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 30.0s
Memory limit: 256M

Problem type

The factorial of a number N, denoted as N!, is equal to the product of all natural numbers up to and including N. For example,

  • 1!=1
  • 2!=1\times2=2
  • 3!=1\times2\times3=6
  • 4!=1\times2\times3\times4=24

Given two numbers K and M, what is the smallest value of N such that N! has at least M factors of K (that is, K^M divides evenly into N!)?

Input Specifications

The standard input will contain 10 datasets. Each dataset contains two integers K, M (2\leq K,M\leq1\text{,}000\text{,}000).

For the first 4 cases, K is prime and K*M\leq 1\text{,}000.

For the first 7 cases, K*M\leq1\text{,}000\text{,}000.

Output Specifications

For each dataset, output the minimum value of N such that N! has at least M factors of K.

Sample Input (Five Datasets Shown)

2 2
2 3
3 1
4 2
10 10

Sample Output

4
4
3
6
45

Comments

There are no comments at the moment.