ABC 414 E — Count A%B=C

考察

a mod b=c>0かつa,b,cが相異なる条件は、1≤b<a≤Nかつaがbの倍数でないことと同値である。このとき0<c<b<aが自動的に成り立つ。

b固定で有効なaはN-b個からbの倍数 floor(N/b)-1個を除いた N-b+1-floor(N/b) 個である。

採用する候補: 全bの式を等差数列和 N(N+1)/2 と divisor summatory function Σ floor(N/b) の差にし、同じ商を区間ごとにまとめる

q=floor(N/l)はr=floor(N/q)まで一定なので、lをr+1へ飛ばせば相異なる商区間はO(sqrt N)個である。

棄却する候補: b=1..Nを全走査して有効a数を足す

一項はO(1)でもN=10^12のloopは不可能で、floor quotientが長い区間で一定になる性質を使っていない。

求める個数は Σ_b(N-b+1)-Σ_b floor(N/b)=N(N+1)/2-Σ_b floor(N/b) と簡潔に分離できる。

floor(N/b)の値がqである最大右端はfloor(N/q)。区間[l,r]の寄与はq(r-l+1)なので、商ごとにまとめて漏れなく加算できる。

S=0,l=1から、q=N/l、r=N/q、S+=q·(r-l+1)、l=r+1をNまで反復する。ans=N(N+1)/2-Sをmod 998244353で出力する。各項を適宜mod化し、O(sqrt N)区間を処理する。

典型の発動条件

商が一定な区間の列挙

発動条件: Σ floor(N/i)を巨大Nで求めるとき。

現在商qから右端N/qを逆算して添字をまとめて進める。

条件の二変数化

発動条件: remainder cがa,bから一意に決まり、distinct条件も大小へ簡約できるとき。

tupleを(a,b)へ射影し、c>0を非倍数条件として数える。

等差数列和

発動条件: 各bに対する全候補a数が線形に変化するとき。

Σ(N-b+1)をN(N+1)/2へ閉形式化する。

問題固有の要素

pairwise distinctは個別除外を数える必要がなく、正のremainderならc<b<aというstrict chainに自動変換される。

別の問題へ持ち帰る視点: 剰余tupleでは商・余りの基本不等式からdistinct条件が冗長になる領域を先に切り分ける。

正当性

相異なる正a,b,cのa mod b=cはb<aと非倍数条件に等しく、cは自動的に0<c<b<aで一意。bごとの候補N−bから倍数floor(N/b)−1を除いた和はN(N+1)/2−Σfloor(N/b)。同商区間[l,N/q]の一括加算は全bを一度覆うので、その差がexact個数になる。

実装上の注意

  • N(N+1)は64 bitを超えるので128 bitまたはmod上のinv2を使う。r=N/qを整数除算し、減算結果を法の非負範囲へ戻す。

復習の核

  • N=3..20を全(a,b,c)列挙し、b=1とb=Nの寄与0、完全平方数付近の商区間境界を確認する。

計算量と制約

時間

O(√N)。floor(N/b)の同商区間をまとめる。

空間

O(1)。

制約との対応

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

出典

分類・前提・執筆情報

掲載状態: 収録済み

Count A%B=C の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

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

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

      学習の位置

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

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

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

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

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題