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$

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

Sample Output 1

Sample Input 2

51090942171709440000

Sample Output 2

Sample Input 3

10888869450418352160768000000

Sample Output 3

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.