2018-09-04から1日間の記事一覧
D - LCM Rush 問題概略 1~Nについて、lcm(i,K)を足し合わせた余りを求めよ。解法 約数は高々1400個しか無いのでgcd(i,k)の値で複数の物を纏められる。 gcd(a,b)=1の時、lcm(a,b) = a * b / gcd(a,b) より bと互いに素であるiの合計 * b / となり、iの合計は…
D - LCM Rush 問題概略 1~Nについて、lcm(i,K)を足し合わせた余りを求めよ。解法 約数は高々1400個しか無いのでgcd(i,k)の値で複数の物を纏められる。 gcd(a,b)=1の時、lcm(a,b) = a * b / gcd(a,b) より bと互いに素であるiの合計 * b / となり、iの合計は…