2020-08-08 A. Orac and LCM ~gcd, lcmと肩のmin, max~ Quiz https://codeforces.com/problemset/problem/1349/A AC https://codeforces.com/contest/1349/submission/89173123 感想 学びの多い問題だった lcm, gcdの関係は、lcm(a,b) x gcd(a,b) = a x b しか知らなかったが、肩のmax, minという類似があることを知った(下記画像) 解説 各aを素因数分解し、素数ごとに肩を管理し(肩=0も含む)、2番目に小さい肩を採用する(画像下) なぜそうなるか、素数pについて、画像中央のような設定で考えてみる これはlcmの表で、lcmは肩のmaxをとるので肩が1番小さいp1は消える gcdを取る時は肩のminを取るので、2番目に小さい肩が採用される 補足 各aの素因数分解はO(sqrt(N))かけても通る