Proficient.
Put your skills to the test.

Problem summary

Sum the values of all base-p digits used to write the N consecutive integers starting at M. Input and output use decimal notation.

Constraints

M,N positive; 2 ≤ p ≤ 16; M+N < 10^16.

Worked example

An independently prepared example for this explanation.

81 20 11

260

Solution analysis

1. Define prefixSum(t) as the digit sum for integers 0 through t−1. The required answer is prefixSum(M+N)−prefixSum(M). Leading zeroes do not affect digit sums.
2. At a position with place value w, digits repeat in cycles of p·w. A full cycle contributes w·p(p−1)/2. For the incomplete cycle, let digit=(t/w) mod p and remainder=t mod w. Its contribution is w·digit(digit−1)/2 + digit·remainder.
3. The example covers base-eleven numbers 74 through 91. The units cycle through 0…10 while the higher digit changes from 7 to 9. Summing independently by place yields 260, without visiting all twenty integers.

Why it works

For each position, the cycle decomposition partitions the t integers into complete blocks containing each digit exactly w times, complete digit groups inside the final block, and a partial final group. The formula counts all groups exactly once. Summing positions counts every digit; subtracting prefixes isolates the interval.

Watch out. The interval ends at M+N−1. Digit A has value 10, not its character code. Use 64-bit arithmetic.

An independently written complete program with standard headers.

#include<iostream>
// Algorithm: Define prefixSum(t) as the digit sum for integers 0 through t−1.
using namespace std;
using Integer=unsigned long long;
Integer prefixSum(Integer limit,Integer base){
    Integer result=0;
    for(Integer place=1;place<limit;place*=base){
        Integer cycle=place*base;
        Integer digit=(limit/place)%base;
        result+=(limit/cycle)*place*(base*(base-1)/2);
        result+=place*(digit*(digit-1)/2);
        result+=digit*(limit%place);
    }
    return result;
}
int main(){
    Integer first,count,base;
    cin>>first>>count>>base;
    cout<<prefixSum(first+count,base)-prefixSum(first,base)<<'\n';
}