Re: Count The Digits

Points: 20
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Given two integers $$n$$ and $$b$$, compute the total number of digits in the sequence $$0_b, 1_b, ... n_b$$ where $$k_b$$ denotes the representation of $$k$$ in base $$b$$.

Input Specification

The first line of the input contains $$1\le t \le 1000$$, the number of test cases. $$t$$ lines follow.

Each test case consists of two integers, $$0 \leq n \leq 10^{16}$$ and $$2 \leq b \leq 36$$.

Output Specification

For each test case, output a single integer: the total number of digits in the sequence.

4
0 10
10 10
1000 10
5 2

Sample Output

1
12
2894
12

• mouad_smi  commented on Nov. 15, 2021, 11:25 a.m. edited

i used this formula (sum += (ll)(floor(log(i)/log(b))+1)) and i looped through all the numbers and it gives me an incorrect answer for this test (10 10 -> 2894 it gives me 2893).

• AkramElOmrani  commented on March 22, 2021, 10:58 p.m. edited

I didn't quite understand how we got 2894 in the 3rd test case any help ?

• mouad_smi  commented on Sept. 17, 2021, 10:48 p.m.

same!

• itsachrafmansari  commented on Sept. 18, 2021, 5:47 p.m. edited

We are counting the total number of digits we need to represent all the K cases in the base B.

As for the 3rd case :

• from 0 to 9 there are 10 numbers, each contains 1 digit
• from 10 to 99 there are 90 numbers, each contains 2 digits
• from 100 to 999 there are 900 numbers, each contains 3 digits
• the number 1000 contains 4 digits

So : (10×1)+(90×2)+(900×3)+(1×4) = 2894