Re: Count The Digits


Submit solution

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.

Sample Input

4
0 10
10 10
1000 10
5 2

Sample Output

1
12
2894
12

Comments


  • 0
    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).

    any help please ?


  • 1
    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 ?


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

      same!


      • 0
        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