ABC 460 E — x + y ≡ x + y

考察

concat(x,y)=x10^d+yなので、concat(x,y)≡x+y mod M は (10^d-1)x≡0 mod M に等しく、yは値ではなく桁数dだけが関係する。

採用する候補: d=1..19ごとに g=gcd(10^d-1,M) を求め、xが M/g の倍数である個数と、範囲内のd桁y個数を掛けて足す。

一次合同式 ax≡0 mod M の解は x≡0 mod M/gcd(a,M) と完全に特徴付けられ、桁数種類は定数個である。

棄却する候補: 全 x,y pairで実際にdecimal連結値を作り合同式を検査する。

候補pairが二乗個で、連結値は64 bitをoverflowし得る。

y項は合同式の両辺で打ち消し合い、10^d倍されたxの差だけが残る。

d桁yの個数は [10^{d-1},10^d-1] と問題のy上限の共通部分長で求められる。

pow10を128 bitまたは飽和で順に更新する。各dでa=10^d-1、step=M/gcd(a,M) とし floor(Xmax/step) をx個数にする。d桁y範囲をclipした個数との積を加算する。

典型の発動条件

decimal連結の代数化

発動条件: concat値の合同条件を数えたいとき。

後半桁数の10冪shiftへ展開して共通項を消す。

一次合同式とgcd

発動条件: ax≡0 mod Mの範囲内解数を求めたいとき。

解のstep M/gcd(a,M) を導いて倍数を数える。

問題固有の要素

文字列表現の連結も桁数別に数式化すると、片方の具体値が条件から消える場合がある。

別の問題へ持ち帰る視点: 零右辺の一次合同式はmodular inverseではなくgcdで解集合の周期を得る。

正当性

d桁yのconcatは10^dx+y。合同の両辺からyを除くと(10^d−1)x≡0で、gcd gによりxはM/gの倍数に限り逆に全て成立する。yの値は桁数だけで関係するので各digit範囲の個数とvalid x数を掛け、互いに素な桁groupを足せば全ordered pairを一度数える。

実装上の注意

  • 10^19はsigned64 bit範囲外なので128 bitまたは上限clipを使う。y=0を含むかと桁数定義を問題通りに扱う。

復習の核

  • concat式からyが消える変形と ax≡0 の解stepを導き、各dのy範囲clipを境界値で確認する。

計算量と制約

時間

各case O(log_{10}N·log M)。桁groupごとのgcdと個数計算。

空間

O(1)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq T \leq 10^4; 1 \leq N \leq 10^{18}; 2 \leq M \leq 10^9; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

x + y ≡ x + y の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 一次合同・CRTで解の類を統合する

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

      主タグ: 一次合同・CRT

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

      学習の位置

      体系上の位置: 一次合同・CRTで解の類を統合する

      • 合同条件の可解性を判定し、逆元・一次合同・CRTで解の類を構成できる。

      先に読む単元:

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

      • 可解性判定を要しない通常の法上加減乗除・高速累乗、および剰余周期だけの利用。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題