ECOO '18 R2 P3 - Factorial

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 Specification

The standard input will contain 10 datasets. Each dataset contains two integers K, M (2 \le K,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

There are no comments at the moment.