Блог пользователя Lucas97

How to compute the sum of the digits of n! (n <= 1e9) ?
Автор Lucas97, история, 8 лет назад, По-английски

Hi guys, today a friend asked me about this problem. He said it was just a random problem that came to his mind. So, I don't know any OJ to submit it. Do you know any way to solve it efficienty? i.e. I know we can compute it using Java or Python, but I'm looknig for something better(Imagine you have 3s as time limit)

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +162 Проголосовать: не нравится

Usually when a new problems comes to your mind you shouldn't put specific constraints for it randomly and immediately, because it's not guaranteed it's solvable in those constraints.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

It looks like even in oeis there is no solution: link

→ Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится -36 Проголосовать: не нравится

.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Spoiler
→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    You clearly didn't understand the problem and of course it will be TLE

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      For smaller n(say, n=1000), maybe it wont be a problem. eg: if v=24.5, we can break up the number into smaller parts(maybe) and then multiply, such as 10^9 * 10^9 * 10^(6.5) . Only the last multiplicand will contribute to the final answer. Although, I'm not exactly convinced how this can be??

      Like Kingofnumbers said, n<=10^9 is not a good solvable limit here.

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My experience tells me that you can solve this type of problem by using math, which will help you reduce numbers of calculation.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think this type of problem won't ask you to calculate n! (n <= 10^9) because it seems impossible to be solved in time. Calculating n! may be a part of calulating the main question.

    → Ответить
»
8 лет назад, # |
← Rev. 4   Проголосовать: нравится -28 Проголосовать: не нравится

Hello, a member of my team used the stirling formula to find number of digits of factorail in the problem UVA 1185 and he got accepted

xd fofao_funk comment in blog http://mirror.codeforces.com/blog/entry/44112?#comment-287711. how to solve your problem and I understand omega(n) time complexity algorithm to sum number of digits of n!.

link to problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3626

reference: https://es.wikipedia.org/wiki/F%C3%B3rmula_de_Stirling

→ Ответить