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$ $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)$ $(2 \leq K \leq 1 000 000, 1 \leq M \leq 1 000 000)$ .

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

For the first 7 cases, $K \times M \le 1\,000\,000$ $K \times M \leq 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)

Copy

Sample Output

Copy

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