ABC 293 F — Zero or One

考察

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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Zero or One の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 整数境界と同値区間を正確に分ける

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 整数境界・同値区間分割

      執筆: abc-explanation-author1.1.1 / revision 1

      学習の位置

      体系上の位置: 整数境界と同値区間を正確に分ける

      • floor(N/i)が一定の最大区間を整数除算で列挙し、O(√N)個の区間へ集約できる。整数根・桁数の境界も誤差なく扱える。

      この解説で扱わないこと:

      • 素因数指数による整数条件の分解。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題