ECOO '18 R2 P3 - Factorial - Olympiads Online Judge

ECOO '18 R2 P3 - Factorial

View as PDF

Submit solution

All submissions

Best submissions

Points: 12 (partial)

Time limit: 13.0s

Memory limit: 256M

Problem type

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

$1! = 1$ ~1! = 1~
$2! = 1 \times 2 = 2$ ~2! = 1 \times 2 = 2~
$3! = 1 \times 2 \times 3 = 6$ ~3! = 1 \times 2 \times 3 = 6~
$4! = 1 \times 2 \times 3 \times 4 = 24$

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

Input Specification

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

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

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

Output Specification

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

Sample Input (Five Datasets Shown)

Sample Output

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