关于在范围内一个位数有几位就能被几整除的个数怎么可以有更运行更快的算法

Question

这个是题目

下面是我做的
使用了内嵌循环怎么修改可以满足时间限制
或许有什么更优的算法吗

请各位指教，谢谢!

Answer 1

这里有一个问题就是10的12次方超过int了，用l和r 用 long long, 在运行下代码试试，有可能错误导致超时
先假设代码没有循环问题，下面有一个优化手段：
每个数字有多少位数的，倒是有一个思路可以把求位数的时间省下来，下面大数据pow10_next也需要用long long

pow10_cur = 算出来l有多少位; 比如l=121，那么 pow10_cur = 3
pow10_next = pow(10,pow10_l+1);//pow10_next = 1000，如果下面的循序i到达下次位数大小，位数+1
for (i=l;i<=r;i++)
{
    if (i < pow10_next ) n = pow10_cur; //n表示位置，大部分位置计算在这里
    else { //更新下个位置，这里基本很少运算
        pow10_cur ++ ;
        n = pow10_cur;
        pow10_next = pow(10, pow10_cur+1);
    }
    //后面判断是否i可以整除位数了
}