A. Orac and LCM ~gcd, lcmと肩のmin, max~

f:id:peroon:20200808055104p:plain

  • 解説
    • 各aを素因数分解し、素数ごとに肩を管理し(肩=0も含む)、2番目に小さい肩を採用する(画像下)
    • なぜそうなるか、素数pについて、画像中央のような設定で考えてみる
    • これはlcmの表で、lcmは肩のmaxをとるので肩が1番小さいp1は消える
    • gcdを取る時は肩のminを取るので、2番目に小さい肩が採用される
  • 補足