题解：UVA12517 Digit Sum

HAPPINESS23333 · 2025-08-04 17:07:11 · 题解

题解：UVA12517 Digit Sum

题目传送门

思路

我们可以计算 0 到 N 的数位和之和以及 0 到 M 的数位和之和，然后相减，最后再加上被减去的 N 的数位和。

就拿 328 这个数来讲吧，计算 0 到 328 的数位和之和，我们可以将它先拆解为 0 到 300 的数位和之和、300 到 328 的数位和之和。

• 先算 0 到 300 的数位和之和：从百位来看，1、2 都被计算了 100 次，3 被计算了 1 次；从十位来看，从 1 到 9 每 100 个数就会被计算 10 次，而 300 就被计算了 30 次；从个位来看，从 1 到 9 每 10 个数就会被计算 1 次，而 300 就也被计算了 30 次，由此得出，计算 0 到 300 的数位和之和的算式为：3 + ( 1 + 2 ) \times 100 + 30 \times [ ( 1 + 9 ) \times 9 \div 2 ] \times 2 = 3003。
• 再算 300 到 328 的数位和之和：可以将它看成 0 到 28 的数位和之和加上少算的 28 次 3。

所以得出：设 0 到 N 的数位和之和为 f(n) ,N 的长度设为 len，第一个数设为 first，除第一个数外后面的数为 behind，就可以得出这样的式子：

当然啦，当 len 为 1 时 f(n) = ( 1 + n ) \times n \div 2。 所以递归就写出来了：

long long solve(long long n){
    if(n<10){
        return (1+n)*n/2;
    }
    long long final_out=0;
    long long v=n;
    long long len=0;
    while(v>0){
        len++;
        final_out+=v%10;;
        v/=10;
    }
    long long first=n/(long long)pow(10,len-1);
    long long behind=n%(long long)pow(10,len-1);
    return first*(behind+1)+solve(behind)+(first-1)*first/2*(long long)pow(10,len-1)+first*(len-1)*(long long)pow(10,len-2)*45;
}

没试过不开 long long，可以去试试看的。

还有一个注意的点，我们这里的函数算的数位和是包含 n 的，所以在之后的相减中要将 N 的数位和加回来（上文说过了）。

最后的最后，提供一下完整的代码吧。

#include<bits/stdc++.h>
using namespace std;
long long solve(int n){
    if(n<10){
        return (1+n)*n/2;
    }
    long long final_out=0;
    long long v=n;
    long long len=0;
    while(v>0){
        len++;
        final_out+=v%10;;
        v/=10;
    }
    long long first=n/(long long)pow(10,len-1);
    long long behind=n%(long long)pow(10,len-1);
    return first*(behind+1)+solve(behind)+(first-1)*first/2*(long long)pow(10,len-1)+first*(len-1)*(long long)pow(10,len-2)*45;
}
int main()
{
    while(true){
        long long N,M;
        cin>>N>>M;
        if(N==M && N==0){
            break;
        }
        long long num=0;
        num=solve(M)-solve(N);
        while(N>0){
            num+=N%10;
            N/=10;
        }
        cout<<num<<endl;
    }
    return 0;
}