题解：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

，就可以得出这样的式子：

f(n) = first \times ( behind + 1 ) +f(behind) + [ ( first - 1 ) \times first \div 2 ] \times 10 ^ { len - 1 } + first \times 10 ^ { len - 2 }\times [ ( 1 + 9 ) \times 9 \div 2 ] \times ( len - 1 )

当然啦，当

len

为

1

时

f(n) = ( 1 + n ) \times n \div 2

。所以递归就写出来了：

CPP

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

的数位和加回来（上文说过了）。

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

CPP

#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;
}

题解：UVA12517 Digit Sum

文章操作

题解：UVA12517 Digit Sum

思路

相关推荐

评论

题解：UVA12517 Digit Sum