AtCoder Beginner Contest 150 D - Semi Common Multiple
問題リンク
https://atcoder.jp/contests/abc150/tasks/abc150_d
問題文は割愛。
これ難しいね。
考察過程。
まず言われた通りに式変形。
A_i/2=B_iとすると
X=2pB_i+B_i=(2p+1)B_i
p=0,1,2,3,......なのでB_iの奇数倍がXになる。
適当にB_iを奇数倍して数を揃えるとそこからは簡単に求まりそう。
最大公約数っぽい？→B_iが1e9ぐらいまではありえるので、LCMがオーバーフローして無理
こういうときは素因数分解してLCMの素因数だけ求める→Nsqrt(A)が通らないので無理
てかそもそもLCM求めたとして奇数倍遷移でいける？→無理なときもある
あーこれは全探索系か？Xの値を決め打ち全探索→でかすぎて無理
とりあえず無理なパターンだけ弾く方針で、そうすると残りは簡単に求まったりするときがあるので
2,3,5とかだと無理だなあ……あ、これ偶数あるとき無理なのでは？→嘘でーす2,6,6とかだと全然作れる。
LCMとりつつLCMとの商を見て偶数なら弾く？(何を言ってるんだ)(コンテスト中は慌てがち)→実装
いやいや違うわ
うーん、てかそもそもLCMでかくなっちゃうからなー……あっM以下じゃん……！
全体のLCMを計算しつつMを超えたらそこで計算打ち切って0を出力でオッケー。
これだとLCMを計算する方針で進めれる。
発想も綺麗だし典型っぽいしABCだしこれ想定解でしょと進めていく。
奇数倍遷移でLCMにならないパターンはどうしようか
そもそも奇数×奇数=奇数、偶数×奇数=偶数、偶数×偶数=偶数
なので今回は奇数の元は奇数のLCMにしかなれない。
もっと言うと偶数の数を調整できない、
あーこれはBに含まれる素因数2の数が同じであることが必要っぽい。
なので最初に2べきの数計算してsetに突っ込んでサイズ確認しておく
LCMが求まったのであとはカウントするだけ
算数苦手だなあ……あーこれは単調性があるので二分探索
個数をnとすると(nは自然数)
{2(n-1)+1}LCM<=Mならokだね。めぐる式書くだけ。
提出→AC
よかったよかった。
難しくて緊張感のある400でした。
