2356.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2356 on 2006-09-13 at 22:03:40 */ 
#include <cstdio>
#include <algorithm>
using namespace std;
 
typedef long long int64;
 
int64 f[10] = { 1 };
 
void stat(int64, int64*);
 
int main()
{
	int64 n[2][10], a, b;
	
	for(int i = 1; i < 10; i++) f[i] = f[i-1]*10;
	while(scanf("%lld %lld", &a, &b) != EOF && a >= 0) {
		memset(n, 0, sizeof(n));
		stat(a-1, n[0]); stat(b, n[1]);
		printf("%lld\n", n[1][0]-n[0][0]);
	}
	
	return 0;
}
 
void stat(int64 n, int64* num)
{
	if(n < 0) { num[0] = -1; return; }
	int bn = upper_bound(f, f+10, n)-f, bit[10];
	for(int i = bn-1; i >= 0; i--)
		for(bit[i] = 0; n >= f[i]; bit[i]++, n -= f[i]) {
			for(int k = 0; k < 10; k++) num[k] += f[i]*i/10;
			for(int k = i; k < bn; k++) num[bit[k]] += f[i];
		}
	num[0] -= bn;
	for(int i = 1; i < bn; i++) num[0] -= f[i-1]*9*(bn-i);
	for(int i = 0; i < bn; i++) num[bit[i]]++;
}