「AtCoder Regular Contest 090F」Number of Digits – 题解

主要思路

这个题还蛮有意思。

首先有个暴力，\(l\) 在 \(10^7\) 内可以直接 two-pointers；如果在 \(10^7\) 以上，那么发现 \(f(r) – f(l) \leq 1\)。那么我们可以考虑枚举这个连续段的长 \(L = x + y\)，其中 \(x\) 是 \(i\) 个 \(0\) 的部分，而 \(y\) 是 \(i + 1\) 个 \(0\) 的部分。有个等式：\(x \times i + y \times (i + 1) = (x + y)i + y = Li + y = S\)。所以枚举 \(L\) 的时候，如果 \(S \bmod L \equiv 0\)，那么说明 \(y = 0\)，你就把 \(10^i\) 内的左端点个数算出来（其实就是多减一个 \(L – 1\)）。如果 \(S \bmod L \neq 0\)，那么说明 \(x, y\) 确定了，那么就直接 ++ 即可。

代码

// ARC090F.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5e7 + 200, mod = 1e9 + 7;

int n, f[MAX_N];

int fpow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i < MAX_N; i++)
        f[i] = f[i / 10] + 1;
    int ans = 0;
    for (int i = 1, j = 1, sum = 0; i < 1e7; i++)
    {
        while (sum < n)
            sum += f[j++];
        if (sum == n)
            ans++;
        sum -= f[i];
    }
    for (int i = 1; i <= n / 8; i++)
    {
        if (n % i == 0)
            // y == 0, t = n / i;
            ans = (0LL + ans + (0LL + fpow(10, n / i) + mod - (fpow(10, (n / i) - 1) + i - 1) % mod) % mod) % mod;
        else
            ans = (0LL + ans + 1) % mod;
    }
    printf("%d\n", ans);
    return 0;
}