Range Sums of Digital Roots
National Olympiad — Regional round (2021 season)
Submission name: suma.cpp
Problem summary
Replace each positive integer repeatedly by its digit sum until one digit remains. Answer sums of these digital roots over index ranges [S,F].
Input
Q followed by Q pairs S F.
Output
One range sum per line.
Constraints
1 ≤ Q ≤ 100; 1 ≤ S ≤ F < 2^60.
Worked example
Input and output for the worked example discussed below.
Input
2 9 13 44 45
Output
19 17
Solution analysis
- Digital roots of positive integers repeat 1,2,…,9. Each full block contributes 45.
- A prefix through n sums to 45floor(n/9)+r(r+1)/2, where r=n modulo 9. Answer [S,F] by prefix(F)−prefix(S−1), with prefix(0)=0.
- For [9,13], roots 9,1,2,3,4 sum to 19; [44,45] gives 8+9=17. Even very large endpoints require only constant-time arithmetic.
Why it works
Digit summation preserves residue modulo 9, determining the 1…9 cycle whose full blocks and tail yield the exact prefix sum.
Complexity: O(1) time per query and O(1) space. Prefixes below 2^60 stay below 5×2^60 and fit signed 64-bit.
Watch out. Multiples of nine have root 9, not zero. Handle S=1 using prefix(0), and use long long.
Commented C++17 solution
An independently written complete program with standard headers.
// Digit summation preserves residue modulo 9, determining the 1…9 cycle whose full blocks and tail yield the
// exact prefix sum.
#include<iostream>
using namespace std;
long long prefix(long long length){
long long remainder=length%9;
return length/9*45+remainder*(remainder+1)/2;
}
int main(){
int queries;
cin>>queries;
while(queries--){
long long left,right;
cin>>left>>right;
cout<<prefix(right)-prefix(left-1)<<'\n';
}
}