ECOO '18 R2 P3 - Factorial

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 13.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 \times 2 = 2
  • 3! = 1 \times 2 \times 3 = 6
  • 4! = 1 \times 2 \times 3 \times 4 = 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 Specification

The standard input contains 10 datasets. Each dataset contains two integers K, M (2 \le K \le 1\,000\,000, 1 \le M \le 1\,000\,000).

For the first 4 cases, K is prime and K \times M \le 1\,000.

For the first 7 cases, K \times M \le 1\,000\,000.

Output Specification

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

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org


Comments


  • 3
    lwale1  commented on June 6, 2022, 4:49 p.m.

    that's the longest time limit I've ever seen