Atcoder ARC090F Number of Digits

记 \(n\) 为题面的 \(S\)。

能发现对于 \(f(l) = 8\)，共有 \(9\times 10^7\) 个数。
此时就已经有 \(8\times 9\times 10^7 > 10^8 = n_{\max}\) 了，就说明不存在 \(f \ge 8\) 的情况，还满足这部分对应的数能全被选满。

所以可以知道对于 \(f(l)\ge 8\) 的情况，只存在 \(f(r) - f(l) = 0 \operatorname{or} 1\) 的情况。

对于 \(f(l)\le 7\) 的情况。
能发现 \(r\) 的上界是 \(10^7 + \frac{10^8}{8}\)，所以这部分直接双指针就行了。

接下来考虑 \(f(l)\ge 8, f(r) - f(l) = 1\) 的情况。
考虑令 \(f(l)\) 选了 \(x\) 个，\(f(r) = f(l) + 1\) 选了 \(y\) 个。
需要先声明的是，在这个位置先不考虑 \(x, y > 0\) 的限制，而认为 \(y\) 可以为 \(0\)，关于这部分将会在后面提到。
那么就能得到 \((x + y)f(l) + y = n\)。
然后这里以 \(x + y\) 为主元，能发现对于固定的 \(x + y\)，其对应的 \(f(l)\) 和 \(x, y\) 都只有 \(1\) 个，就是 \(\begin{cases}y = n\bmod (x + y)\\ x = (x + y) - y\\ f(l) = \frac{n - y}{x + y}\end{cases}\)。

于是转而去考虑 \(x + y\) 能有多少种可能。
这是好算的，因为 \(x + y\le \frac{n}{f(l)}\)，而因为 \(f(l)\ge 8\)，所以 \(x + y\le \frac{n}{8}\)，对应的就有 \(\lfloor \frac{n}{8} \rfloor\) 种选法。

最后来考虑 \(f(l)\ge 8, f(r) - f(l) = 0\) 的情况。
这时候就已经确定了 \(f(l)\) 了，就相当于是已经知道需要的个数 \(x\) 了。
那么显然答案就为 \(9\times 10^{f(l) - 1} - x + 1\)，但注意到，在前文的时候提到了误给 \(y = 0\) 时加了 \(1\) 的贡献，而其对应的应该就是这种 \(f(r) - f(l) = 0\) 的情况，所以实际算贡献的时候应该算为 \(9\times 10^{f(l) - 1} - x\)。
这部分可以 \(\mathcal{O}(\sqrt{n} + d(n)\log n)\)。

时间复杂度 \(\mathcal{O}(\frac{n}{b} + \sqrt{n} + d(n)\log n)\)，其中 \(B = 8\)，\(d(n)\) 表示 \(n\) 的因子个数。

#include<bits/stdc++.h>
using ll = long long;
constexpr ll mod = 1e9 + 7;
inline ll qpow(ll a, ll b, ll v = 1) {
   while (b)
      b & 1 && (v = v * a % mod), b >>= 1, a = a * a % mod;
   return v;
}
ll ans;
const int limn = (int)1e7 + (int)1e8 / 8, R = (int)1e7;
int f[limn + 10];
int main() {
   for (int i = 1, l = 1, r = 10; i <= 8; i++, r = std::min(l * 10, limn))
      while (l < r) f[l++] = i;
   int n; scanf("%d", &n);
   for (int i = 1, j = 0, sum = 0; f[i] <= n && i < R; i++) {
      while (sum + f[j + 1] <= n) sum += f[++j];
      if (sum == n) (++ans) %= mod;
      sum -= f[i];
   }
   (ans += n / 8) %= mod;
   auto calc = [&](int fx) {
      int l = n / fx;
      ll len = 9ll * qpow(10, fx - 1) % mod;
      (ans += mod + len - l) %= mod;
   };
   for (int i = 1; i * i <= n; i++) if (n % i == 0) {
      if (i >= 8) calc(i);
      if (n / i >= 8 && i != n / i) calc(n / i);
   }
   printf("%lld\n", ans);
   return 0;
}