i_am_eating_wa_and_tle's blog

Help needed in a number theory problem?
By i_am_eating_wa_and_tle, history, 7 years ago, In English

UPD:Got AC

PDF LINK: http://lightoj.com/volume_showproblem.php?problem=1138&language=english&type=pdf Problem link: http://lightoj.com/volume_showproblem.php?problem=1138

I think the solution is the number of 5s as prime factor in N! But how to calculate them faster.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't read the problem, but If u are looking for the highest power of prime p in factorization of the factorial of a number, it can be done using Legendre's Formula

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    PROBLEM STATEMENT

    You task is to find minimal natural number N, so that N! contains exactly Q zeroes on the trail in decimal notation. As you know N! = 1*2*...*N. For example, 5! = 120, 120 contains one zero on the trail.

    INPUT

    Input starts with an integer T (≤ 10000), denoting the number of test cases.

    Each case contains an integer Q (1 ≤ Q ≤ 108) in a line.

    OUTPUT

    For each case, print the case number and N. If no solution is found then print 'impossible'.

    Sample input

    3

    1

    2

    5

    Sample output

    Case 1: 5

    Case 2: 10

    Case 3: impossible

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can use the formula described by MazzForces to calculate the number of zeroes at the end N! by using 'p' as 5. Now instead of checking all numbers in [0,5Q](notice how we decide the upper bound) to find which number's factorial would yield you Q number of zeroes you can use binary search which will give you a complexity of log2(Q) (Since you'll go over log(Q) values in binary search and for each such value spend log(Q) time to apply legendre's formula) per test case which would easily pass in time.

      → Reply