ABC259 E - LCM on Whiteboard (500)
$ a_iを$ 1に書き換えた際に新しい最小公倍数が作られるか考えると、$ a_iがある素数$ pについて他のどの数よりも$ eが大きければ新しい最小公倍数が作られる
最小公倍数は$ \prod_i p_i^{\max e_i}なので単独で最大で無ければ$ \max e_iが変わらない
それぞれの素数毎に以下を行う
$ eと$ iを記録
$ eの降順でソート
それが単独で最大ならそのインデックスについてマーク
マークされている数に1足した値と$ Nの小さい方が答え
足した1は変化しない所を1にした場合の分