7K12 blog

猫でも分かるアルゴリズム解説

ABC150 D - Semi Common Multiple

f:id:tkr987:20200404172428p:plain

https://atcoder.jp/contests/abc150/submissions/15845505

  • 偶数  a_{k} 2a'_{k} にする
  • 小数を整数にする  2a'_{k} (P+0.5) a'_{k} (2P+1)
  •  a_{k}素因数分解したとき因数2の個数が全て等しい必要がある
  •  a'_{k}のlcmだが、偶数倍はカウントしないので答えは約半分の個数になる

f:id:tkr987:20200404180139p:plain

青difなので数学的センス必須。まず、小数は扱いづらいので2倍して整数にする。全ての a'_{k} (2P+1)がXになることから a'_{k}素因数分解したとき(または a_{k}素因数分解したとき)2の因数の個数が等しい必要がある。

[1,M]に存在する a'_{k}のlcmの公倍数の個数が答えだが、偶数倍はカウントしないため正確には半分くらいの値を出力する。このとき、単純に2で割っても1少ない個数が出力される場合があり、(long long)ceil((double)M / (double)lcm / 2.0)を出力するのが正しい。