考察
d≥3桁では基数bごとの可能値区間[b^(d-1),Σb^i]が互いに交わらず、Nに対する候補bは高々一つである。
採用する候補: 桁数列挙と整数(d-1)乗根候補の検査
d=2を別処理し、各d≥3で最大b^(d-1)≤Nのbだけを実際に基数変換すればよい。
棄却する候補: 全基数2..Nを試す
Nは10^18で線形列挙できない。
Σ_(i=0)^(d-1)b^i < (b+1)^(d-1)により隣接基数のd桁01表現範囲が分離する。
d=2..floor(log2 N)+1を列挙し、d=2の候補N,N-1を処理する。d≥3は整数二分探索でbを求め、Nをb進除算して全桁0/1か検査し重複なく数える。
典型の発動条件
整数k乗根
発動条件: 巨大整数Nに対しb^k≤Nの最大bを求める。
オーバーフローを抑えた比較で二分探索する。
表現範囲の分離
発動条件: 基数候補が多そうだが桁数固定で値域が離れる。
O(log N)個の桁数を列挙し、各桁数では表現範囲の非交差性から候補基数を高々一つへ絞る。
問題固有の要素
01桁という疎な表現条件が、二項定理によって基数ごとの値域を非交差にする。
別の問題へ持ち帰る視点: 基数探索は桁数固定時の表現可能区間の重なりを調べる。
正当性
d≥3桁の01表現が存在するならb^{d−1}≤N≤Σ_{i<d}b^i。後者は(b+1)^{d−1}未満なので異基数の可能域は重ならず、その桁数で調べるbは高々一つ。d=2のN,N−1と全d≥3の候補を取り、実際の除算で全桁0/1を確認すれば全可能基数を尽くす。
実装上の注意
- b≥2、d=2の候補重複、N=2境界を処理し、冪計算はN超で飽和する。
復習の核
- 小Nで全基数を試し、2桁候補、同じbが別dで数えられないこと、最大桁数を確認する。
計算量と制約
時間
各case O((log N)³)を上界とする。桁数ごとに整数二分探索と飽和冪評価を行う。
空間
O(log N)。候補基数を重複除去する。
制約との対応
公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1 \leq T \leq 1000; 2 \leq N \leq 10^{18}; All values in the input are integers.
出典