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行)

ARC090の他の問題 C D E

自己紹介

プログラミングとか合成音声とか
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

最終更新日:2023.03.05

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

寄付モドキ

0冂から10000冂まで
詳しくはこちら