n位数，总共有0~10^n-1共计10^n个数
那么所有数出现的总次数变为n*(10^n)个数
1出现的次数便是十分之一，所以n位数中，1出现的次数为n*10^(n-1)
知道这一个后，接下来就方便求了。

举个例子就方便理解了 3125

从头到尾for一遍

3:
那么便有三组1000以内的：0~999,1000~1999,2000~2999
1000以内的1的个数为300，所以共有3*300=900
但是又因为1000~1999中千位上的1也要算进去，有1000个
所以0~2999中总共有900+1000=1900个1

1:
只有一组完整的100以内的，即0~99（对应3000~3099），在这最后二位数中1出现的次数为20个
又因为31xx中百位上的1也要算进去，但并不是+100，而是25+1，对应3100~3125这26个
所以3000~3099以及31xx共计46个1
（PS：这里还没统计31xx中xx出现的1）

2：
有两组10以内的，即0~9，10~19（对应3100~3109,3110~3119）
这中间最后一位数上1的出现次数为2,3101,3111
又因为311x中十位上的1也要算进去，出现了10次
所以总共12次
（PS：这里还没有统计312x中x位上的1）
5：
1只出现了1次

所以总共1900+46+12+1=1959

表达能力有限，如果还不懂的童鞋一定要自己动手写写

http://www.liuchuo.net/archives/2305
该博客的解题思路比我要好，统计的是每个位上1出现的次数（相当于该位上为1的数有多少个），然后各个位累加起来即可。

然而题目中n<=2^30，应该为long long，但是该博客的代码中int也可以，估计是样例不严谨吧。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <cmath>
using namespace std;
char num[20];

int main()
{
    scanf("%s",num);
    int len=strlen(num);
    long long ans=0;
    for(int i=0;i<len-1;i++){
        int a=num[i]-‘0‘;
        int digit=len-i-1; //在a右边的位数
        for(int j=1;j<=a;j++){
            ans+=(pow((long long)10,digit)*(digit)+0.5)/10;  //注意要加个0.5，保证结果精度正确
            if(j==1){
                if(a!=1)
                    ans+=pow((long long)10,digit)+0.5;
                else
                    ans+=atoll(num+i+1)+1; //+1是10..0的情况
            }
        }
    }
    if(num[len-1]-‘0‘>=1)
        ans++;
    printf("%d\n",ans);
    return 0;
}

View Code

PAT甲题题解-1049. Counting Ones-数学问题