https://atcoder.jp/contests/abc152/submissions/12833879
- 全ての積が同じ値になる⇔全てBiで割り切れる⇔lcm(Ai)
- lcmがインフレするときは素因数分解を利用する
大きいAiと小さいBiの積にする必要があると分かるが、更に詰めていくと「全ての積が同じ値(なるべく小さな値)になる⇔全てBi(なるべく小さな値)で割り切れる⇔lcm(Ai)」となる。ただし、lcm(Ai)がを簡単に超えてしまうので、mod上でlcmするように工夫する必要がある。これは素因数分解を使うことで解決する。素因数分解したとき各因数の指数最大を掛け算すると最小公倍数になる。計算量はになる。