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!!!
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 160 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | Dominater069 | 154 |
| 8 | awoo | 154 |
| 10 | luogu_official | 151 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Dec/23/2024 08:31:40 (f1).
Desktop version, switch to mobile version.
Supported by
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 ⌈ lg(N + 1)!⌉ 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.