转载自：http://www.cnblogs.com/cyjb/p/digitOccurrenceInRegion.html
计算右数第 i位包含的 X 的个数时： 1. 取第 i位左边（高位）的数字，乘以 10^(i−1)，得到基础值 a。 2. 取第 i位数字，计算修正值： 如果大于 X，则结果为 a+10^(i−1)。 如果小于 X，则结果为 a。 如果等 X，则取第 i位右边（低位）数字，设为 b，最后结果为 a+b+1。 相应的代码非常简单，效率也非常高，时间复杂度只有 O(log2n) 。
当 X = 0 时，规律与上面给出的规律不同，需要另行考虑。 最主要的区别是，最高位中永远是不会包含 0 的，因此，从个位累加到左起第二位就要结束，需要将上面代码中 for 循环的判断条件改为 k / 10 != 0。 其次是，第 i位的基础值不是高位数字乘以 10^(i−1)，而是乘以10^(i−1) -1
#include <iostream> using namespace std; //计算x在num中出现的次数 int countNumbers(int num, int x){ int times = 0, k, temp; for(int i=1; k=num/i; i*=10){ if(x!=0) times += k / 10 * i; if(x==0) times += (k / 10 - 1) * i; temp = k % 10; if(temp > x) times += i; else if(temp == x) times += num - k * i + 1; } return times; } int main(){ int num; cin>>num; cout<<countNumbers(num, 0)<<endl; return 0; }