UVa 1640 - The Counting Problem（数论）

链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4515

题意：

给出整数a、b，统计a和b（包含a和b）之间的整数中，数字0,1,2,3,4,5,6,7,8,9分别出现了多少次。1≤a,b≤1e8。

分析：

解决这类题目的第一步一般都是：令f(n,d)表示0～n中数字d出现的次数，则所求的就是f(b,d)-f(a-1,d)。
例如，要统计0～234中4的个数，可以分成几个区间：

范围                    模板集
0~9                    *
10~99                **
100~199            1**
200~229            20*,21*,22*
230~234            230,231,232,233,234

上表中的“模板”指的是一些整数的集合，其中字符“*”表示“任意字符”。例如，1**表示以1开头的任意3位数。
因为后两个数字完全任意，所以“个位和十位”中每个数字出现的次数是均等的。
换句话说，在模板1**所对应的100个整数的200个“个位和十位”数字中，0～9各有20个。
而这些数的百位总是1，因此得到：模板1**对应的100个整数包含数字0，2～9各20个，数字1有120个。
这样，只需把0～n分成若干个区间，算出每个区间中各个模板所对应的整数包含每个数字各多少次，就能解决原问题了。

代码：

 #include <cstdio>

 #include <cstring>

 const int UP = ;

 int pow10[UP], amt[UP];

 int f(int n, int d) {

     int res = ;

     char s[];

     sprintf(s, "%d", n);

     int len = strlen(s);

     for(int i = ; i < len; i++) {

         if(i == ) res++;

         else {

             res +=  * amt[i-];

             if(d > ) res += pow10[i-];

         }

     }

     int pre = ;

     for(int i = ; i < len; i++) {

         int L = , R = s[i]-'';

         if(i ==  && len > ) L = ;

         for(int digit = L; digit < R; digit++) {

             res += amt[len--i] + pre * pow10[len--i];

             if(digit == d) res += pow10[len--i];

         }

         if(s[i]-'' == d) pre++;

     }

     return res + pre;

 }

 int main() {

     pow10[] = ;

     for(int i = ; i < UP; i++) {

         pow10[i] = pow10[i-] * ;

         amt[i] = pow10[i] * i / ;

     }

     int a, b;

     while(scanf("%d%d", &a, &b) && a) {

         if(a > b) b += a, a = b-a, b -= a;

         printf("%d", f(b,) - f(a-,));

         for(int i = ; i < ; i++) printf(" %d", f(b,i) - f(a-,i));

         printf("\n");

     }

     return ;

 }

UVa 1640 - The Counting Problem（数论）的相关教程结束。