For quite some time, I had the doubt about how many digits had an mathematical operation like this: A*B or A!, and searching in internet, i found how to do this using log, but i found the problem Python Brute Force, that ask for the number of digit to the following operation: 1*1!+2*2!+....+N*N!. I don't know how to count the number of digit to the sum of terms, like A+B. Maybe this problem is just transform the operations, but i don't see how to do that. thank for the help!!!
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | djm03178 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 12.11.2024 22:44:50 (l3).
Десктопная версия, переключиться на мобильную.
При поддержке
You can show that 1 * 1! + 2 * 2! + ... + N * N! = (N + 1)! — 1. Now, the number of digits of (N + 1)! — 1 is the same that (N+1)!, because (N + 1)! is never a power of ten.
Maybe if you rewrite it, this will help you.
1*1! + 2*2! + ... + N*N!=1*(1 + 2*(2 + 3*(3 + ... + N*(N)Because k * k! can be rewritten as (k + 1 - 1) * k! = (k + 1)! - k! your sum telescopes to (N + 1)! - 1. Now the number of digits in (N + 1)! - 1 is equal to the number of digits of (N + 1)! because N! is not a power of ten for any N > 1. Now you need to find the smallest k such that (N + 1)! < 10k then the number of digits will be k. The inequality can be rewritten as lg(N + 1)! < k, so the smallest solution is
Unable to parse markup [type=CF_TEX]
but lg(N + 1)! = lg(1 * 2 * 3 * ... * (N + 1)) = lg1 + lg2 + lg3 + lg4 + ... + lg(N + 1). Floating point numbers can be a bit imprecise(maybe there is another method for solving that inequality), but if you precompute the values sequentialy for all N, you'll be able to answer in O(1) for a query. Also if you work in other base than base 10, then instead you should solve the inequality (N + 1)! < basek.Very nice problem, i understand now. Thank everybody.