【例46.2】 数字统计

解题思路

按十进制位权统计1～N中7出现次数。对位权f，令高位high=N/(10f)、当前位cur、低位low。完整周期贡献high*f，当前位>7再加f，等于7再加low+1。区间答案为F(R)-F(L-1)。

正确性说明

计算规则直接来自题目定义。按所述顺序处理时，已完成部分的结果被准确保存在累加量、计数或当前状态中；下一步只加入新增贡献。最终得到完整要求的结果。

易错点

统计出现次数而非含7的整数个数；7不是0，无前导零修正。

复杂度

时间O(log R)，空间O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

long long count7(long long n) {
    if (n <= 0)
        return 0;
    long long ans = 0;
    for (long long f = 1; f <= n;) {
        long long q = n / f, cur = q % 10, high = q / 10, low = n % f;
        ans += high * f;
        if (cur > 7)
            ans += f;
        else if (cur == 7)
            ans += low + 1;
        if (f > n / 10)
            break;
        f *= 10;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long L, R;
    cin >> L >> R;
    cout << count7(R) - count7(L - 1) << "\n";
    return 0;
}