Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 293 F問題 Zero or One

AtCoder ABC293 ABC 500 pts F問題

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$2$ 以上の整数 $b$ のうち, 以下を満たすような整数の数を求めよ.

$N$ を $b$ 進法で表すと, 全ての桁について, 「その桁が $0$ または $1$ 」が成り立つ.

$T$ 個のテストケースについて答えよ.

制約

$1 \leq T \leq 1000$
$2 \leq N \leq 10^{18}$

解法

まず, $b \gt N$ とすると, $N$ の $b$ 進法が $(N)$ となり, $N \geq 2$ の制約から, $b \gt N$ は条件を満たさない.

よって, $b \leq N$ の場合を調べれば良い.

正の整数 $D$ を固定する. 次のような方針で調べる.

$d \leq D$ とする. $b$ 進法で表すと $d$ 桁になるような $b$ についてまとめて計算する.

このとき, $d$ 桁なので, 可能な $b$ 進法の表し方は $2^{d-1}$ 通りである. よって, 各表し方について, 二分探索を利用することにより, その表し方を達成するような $b$ が存在するか? 存在するならばそのような $b$ は何か? ということを $O(d \cdot \log N)$ 時間で計算できる.

よって, $d$ のときは $O(d \cdot 2^d \log N)$ 時間で列挙できる.

これを $2$ 以上 $D$ 以下の整数 $d$ 全てに対して行うことで, $D$ 桁以下の場合を処理できた.

ここまでの計算量は $O(D^2 2^D \log N)$ 時間である.

$(D+1)$ 桁以上の場合について, このような $b$ は $b^D \leq N$ を満たす. よって, $b \leq \sqrt[D]{N}$ を満たす. よって, このような $b$ 全てに対して愚直に判定すれば良い.

このパートの計算量は $O(\log N \sqrt[D]{N})$ 時間である.

よって, 合計で $O( (D^2 2^D+\sqrt[D]{N}) \log N)$ 時間/テストケースである. $N \leq 10^{18}$ という制約化では, $D=6$ が最も高速になる.