AtCoder Regular Contest 090 F - Number of Digits题目链接Description题解Code

题目链接

Description

For a positive integer (n), let us define (f(n)) as the number of digits in base (10).

You are given an integer (S(1≤S≤10^8)). Count the number of the pairs of positive integers ((l,r)) ((l≤r)) such that (f(l)+f(l+1)+…+f(r)=S), and find the count modulo (10^9+7).

题解

分两种情况讨论。

(1. f(l)leq 7)

则至多有(10^8/8=12500000)个八位数，所以(rleq 22500000).

因此，可以预处理出(f[1..22500000])，然后采用 尺取法 得到 当(f(l)leq 7)时 的((l,r))组数.

(2. f(l)geq 8)

此时，由 (S) 的限制，易知 (f(r)-f(l)leq 1).

令 (t=r-l+1)，枚举 (t)

若 (f(l)==f(r))

则显然要求 (t|S),

记(N)位数的个数右 (D_N) 个，则符合要求的 ((l,r)) 组数为 (D_{frac{S}{t}}-t+1)

若 (f(r)-f(l)==1)

设 (len=f(l)) 且长度为 (len) 的数字有 (x) 个，长度为 (len+1) 的数字有 (y) 个，则有
[begin{cases} x+y=t\ x*len+y*(len+1)=S end{cases} ]
其中(len=lfloorfrac{S}{t}rfloor).
记(S=tq+r (0leq rlt t))
则方程组可转化为
[begin{cases} x+y=t\ xq+y(q+1)=tq+r end{cases} ]
所以有
[begin{cases} x=t-r=t-S%t\ y=r=S%t end{cases} ]
即对每个(t)此时有且仅有一组解。

统计上述三部分的答案，即为最终答案。

Code

#include <bits/stdc++.h>
#define lim1 10000000
#define lim2 22500000
using namespace std;
typedef long long LL;
int f[lim2+10];
const LL mod = 1e9+7;
void init() {
    int l = 1, r = 10;
    for (int k = 1; k <= 7; ++k) {
        for (int i = l; i < r; ++i) f[i] = k;
        l = r; r *= 10;
    }
    for (int i = lim1; i <= lim2; ++i) f[i] = 8;
}
LL poww(LL a, LL b) {
    LL ret = 1;
    while (b) {
        if (b & 1) (ret *= a) %= mod;
        (a *= a) %= mod;
        b >>= 1;
    }
    return ret;
}
LL count1(LL x) {
    int l = 1, r = 1, ret = 0; LL sum = 0;
    while (true) {
        while (r <= lim2 && sum < x) sum += f[r++];
        if (sum < x) break;
        if (sum == x) (ret += 1) %= mod;
        sum -= f[l++];
        if (l == lim1) break;
    }
    return ret;
}
LL count2(LL x) {
    LL upp = x/8,
        ret = upp;
    for (int t = 1; t <= upp; ++t) {
        if (x % t == 0) {
            int len = x / t;
            LL sub = 9 * poww(10, len-1) % mod;
            (sub += mod - t) %= mod;
            (ret += sub) %= mod;
        }
    }
    return ret;
}
int main() {
    init();
    LL n;
    scanf("%lld", &n);
    LL ans1 = count1(n), ans2 = count2(n);
    printf("%lldn", (ans1+ans2)%mod);
    return 0;
}