ARC090 F : Number of Digits(900)
作成日：2018.02.02
最終更新日：2018.02.02
問題概要
$l$以上$r$以下の整数の十進法での桁数の総和が$S$に等しいような正の整数の組$(l,r)$の個数を$10^9 + 7$で割った余りを求めよ。
制約
$1 \leq S \leq 10^8$
考え方
$l$や$r$の具体的な値は不要な情報なので桁数ごとに考えれば良い。
$k$桁の数は$(9 \times 10^{k-1})$個あることを考えると、桁数が十分大きければ$l$と$r$の桁数は$1$以下となる。
$l$と$r$の桁数の差が必ず$1$以下になる桁数では$k$$\times 9$$\times 10^{k-1}$$\gt S$を満たすから、$k \geq 8$の時十分大きいと言える。
まず$l$が$8$桁未満である時を考える。
条件を満たす$(l,r)$は$l$が大きくなるほど$r$も大きくなり、$r$は$\frac{S-7}{8}$以下であるから尺取り法を用いた全探索でも十分高速である。
次に$l$が$8$桁以上で$k$桁である時を考える。
$l$と$r$の桁数が等しい時は、$k$が$S$の約数の時のみ条件を満たす組が存在し、$r-l+1$$= S/k$となる。
これを満たす組の個数は$9 \times 10^{k-1}$$- S/k + 1$である。
$l$と$r$の桁数が$1$違う時、$l$以上$r$以下の範囲にある$k$,$(k+1)$桁の整数の数をそれぞれ$x$,$y$とすると、$kx$$+(k+1)y$$=S$が成り立つ。
この方程式の一般解は、パラメータを$p$として$x = p(k+1) - S$,$y = S - pk$である。
$x$,$y$は$1$以上の整数でなければならないことから、$\frac{S+1}{k+1}$$\leq p$$\leq \frac{S-1}{k}$でなければならない。
この不等式を満たす整数$p$の数だけ答えがあるが、すべての$k$について試すと間に合わない*ので工夫する。
$k$を動かしていった時の$p$の範囲は$p \leq \frac{S-1}{8}$であるが、$\frac{S-1}{k}$$\lt p$$\lt \frac{S+1}{k}$の範囲は除外されている。
この除外される範囲の中で整数となり得るのは$S/k$だけである。
$p$は正の整数であることが不等式から分かるから、$S/k$が整数となる回数、すなわち$S$の$8$以上の約数の個数を$S/8$から引いたものを答えに加算すれば良い。
約数の列挙は$O(\sqrt S)$でできるから十分高速である。
* 整数$p$が存在するのは$k \leq S/2$の時であるから、その範囲に限定して試すと$1$secで通った。
ソースコード
マクロ等はこちら
const LL mod = 1e9 + 7;
LL S;
int d[10];
LL pw(LL x , LL y){
LL res = 1;
LL z = x;
for(LL i = y ; i > 0 ; i >>= 1){
if(i&1) (res *= z) %= mod;
z = z * z % mod;
}
return res;
}
int main(){
cin >> S;
LL ans = 0;
int j = 1;
int x = 1 , y = 1;
LL z = 0;
d[0] = 1;
repp(i,0,9) d[i+1] = d[i] * 10;
repp(i,1,1e7){
if(i == d[x]) ++x;
while(z < S){
z += y;
++j;
if(j == d[y]) ++y;
}
if(z == S) ++ans;
z -= x;
}
(ans += S/8) %= mod;
for(LL i = 1 ; i * i <= S ; ++i){
if(S%i) continue;
if(i >= 8){
(ans += 9 * pw(10,i-1) - S/i + 1) %= mod;
--ans;
}
if(S/i >= 8 && i * i < S){
(ans += 9 * pw(10,S/i-1) - i + 1) %= mod;
--ans;
}
}
if(ans<0) ans += mod;
cout << ans << endl;
return 0;
}解法まとめ
$l \lt 10^7$の範囲では尺取り法により全探索する。(23-32行)
$l \geq 10^7$の範囲では、$S/8$に$S$の$8$以上の約数$k$それぞれにおいて$9 \times 10^{k-1}$$+ S/k + 1$を足して$1$を引いたものが答えである。(33-44行)