ICPC NAQ 2016 G - Inverse Factorial - Olympiads Online Judge

ICPC NAQ 2016 G - Inverse Factorial

Points: 10

Time limit: 0.6s

Memory limit: 1G

Problem type

ICPC North America Qualifier 2016, Problem G

A factorial $n!$ $n!$ of a positive integer $n$ $n$ is defined as the product of all positive integers smaller than or equal to $n$ $n$ . For example,

$\displaystyle 21! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot 21 = 51\,090\,942\,171\,709\,440\,000$ $21! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot 21 = 51 090 942 171 709 440 000$

It is straightforward to calculate the factorial of a small integer, and you have probably done it many times before. In this problem, however, your task is reversed. You are given the value of $n!$ $n!$ and you have to find the value of $n$ $n$ .

Input Specification

The input contains the factorial $n!$ $n!$ of a positive integer $n$ $n$ . The number of digits of $n!$ $n!$ is at most $10^6$ $10^{6}$ .

Output Specification

Output the value of $n$ $n$ .

Sample Input 1

Copy

Sample Output 1

Copy

Sample Input 2

Copy

51090942171709440000

Sample Output 2

Copy

Sample Input 3

Copy

10888869450418352160768000000

Sample Output 3

Copy

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

4

DarthVader336 commented on March 19, 2018, 10:29 p.m.

The time control is quite tight.

4

aeternalis1 commented on March 19, 2018, 10:41 p.m.

You have not implemented the correct solution to this problem. Both Java's and Python's support for large integers still doesn't allow for direct brute-forcing to get the answer. Try thinking of a different approach.