7K12 blog

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

ABC152 E - Flatten

f:id:tkr987:20200610205001p:plain

https://atcoder.jp/contests/abc152/submissions/12833879

  • 全ての積が同じ値になる⇔全てBiで割り切れる⇔lcm(Ai)
  • lcmがインフレするときは素因数分解を利用する

f:id:tkr987:20200610205513p:plain

大きいAiと小さいBiの積にする必要があると分かるが、更に詰めていくと「全ての積が同じ値(なるべく小さな値)になる⇔全てBi(なるべく小さな値)で割り切れる⇔lcm(Ai)」となる。ただし、lcm(Ai)が 10^9を簡単に超えてしまうので、mod上でlcmするように工夫する必要がある。これは素因数分解を使うことで解決する。素因数分解したとき各因数の指数最大を掛け算すると最小公倍数になる。計算量はO(N\sqrt A_i)になる。

http://9871225.blog.fc2.com/blog-entry-393.html