ABC 230 E — Fraction Floor Sum

考察

i が大きくなると floor(N/i) は単調に減り、同じ商を取る i が長い連続区間としてまとまる。

商が k となる整数 i の個数は floor(N/k)−floor(N/(k+1)) で求まり、小さい商は値ごとに一括加算できる。

棄却する候補: i=1 から N まで順に floor(N/i) を計算して足す。

N が 10 の 12 乗まであるため、N 回の除算を実行できない。

採用する候補: sqrt(N) 以下の商は出現回数でまとめ、それより大きい商は対応する小さい i を一つずつ処理する。

商と添字の少なくとも一方が sqrt(N) 以下になる双曲線の性質により、両側を合わせても平方根程度の項だけで済む。

全ての i を走査する代わりに、floor(N/i) の値が同じ区間を数えるという商側からの集約へ視点を移す。

整数双曲線 xy≤N の格子点数え上げとして、小さい商の頻度集約と小さい除数の直接和を境界 floor(sqrt(N)) で分割する。

典型の発動条件

floor 商の平方根分割

発動条件: floor(N/i) を i の広い範囲で集約して和や頻度を求めるとき。

商 k の出現個数を除算二回の差で求め、大きい商側は小さい i だけ直接処理する。

問題固有の要素

k₀=floor(sqrt(N)) とすると、商が k₀+1 以上の i は N/(k₀+1) 以下に限られ、集約側との重複なしに直接列挙できる。

別の問題へ持ち帰る視点: 商と除数の対称性を使う分割では、境界の等号を式で確認して二重計上を避ける。

正当性

s=floor√Nとしてi≤sは直接足す。i>sの商q≤sについてfloor(N/(q+1))<i≤floor(N/q)をi>sへ制限して個数を数える。この二領域は互いに素で全iを覆い、各商の寄与を一度だけ足す。

実装上の注意

  • 平方根は浮動小数に頼らず整数として補正し、k₀²≤N<(k₀+1)² を満たすことを確認する。
  • 答えは 32 bit を超えるため 64 bit 整数を使い、二つの和の添字範囲を境界で重ねない。

復習の核

  • floor(N/i) が並んだら、値の種類数と同値区間の端点 floor(N/k) を先に調べる。

計算量と制約

時間

O(√N)。

空間

O(1)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 10^{12}; N is an integer.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Fraction Floor Sum の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

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

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

      学習の位置

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

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

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

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

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題