ICPC NAQ 2016 G - Inverse Factorial

View as PDF

Submit solution

Points: 10
Time limit: 0.6s
Memory limit: 1G

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
ICPC North America Qualifier 2016, Problem G

A factorial n! of a positive integer n is defined as the product of all positive integers smaller than or equal to 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! and you have to find the value of n.

Input Specification

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

Output Specification

Output the value of n.

Sample Input 1

120

Sample Output 1

5

Sample Input 2

51090942171709440000

Sample Output 2

21

Sample Input 3

10888869450418352160768000000

Sample Output 3

27
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments


  • 4
    DarthVader336  commented on March 19, 2018, 6:29 p.m.

    The time control is quite tight.


    • 3
      aeternalis1  commented on March 19, 2018, 6: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.