考察
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.
出典