2022-03-17 アルゴリズムと数学 演習問題集 091, 092, 093 を解いた
アルゴリズムと数学 演習問題集 091 - How Many Ways? を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_br
N <= 100 から (a, b, c) の組み合わせを全探索しても 10^6 なので間に合う。素直に三重ループの中で a + b + c = X の判定をして個数を数えれば良い。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30187985
アルゴリズムと数学 演習問題集 092 - Beautiful Rectangle を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bs
N <= 10^12 なので縦と横の組み合わせを全探索では間に合わない。求めるのは H * W = N なので N の約数を列挙する。 N の約数は x * x <= N の範囲まで x を探索すればいいので \sqrt{N} になる。これは 10^6 なので間に合う。
1 から x * x <= N の範囲で x を順に調べて N % x == 0 なものについて x * 2 + (N / x) * 2 の最小値を求めれば良い。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30188078
アルゴリズムと数学 演習問題集 093 - Large LCM（★3） を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/typical90_al
競プロ典型 90 問の 38 日目と同じ問題だ (https://atcoder.jp/contests/typical90/tasks/typical90_al) 。
LCM(A, B) を求める。 10^18 を超える場合は Large と出力する。
LCM(A, B) = A * B / GCD(A, B) で GCD(A, B) = if A == 0 then B else GCD(B, A % B) 。
オーバーフローに注意する必要がある。 A * B / GCD(A, B) とすると A * B の時点でオーバーフローしてしまう可能性がある。 A / GCD(A, B) * B としてなるべく値が小さくなるようにする。A / GCD(A, B) と B の掛け算部分はこのままだとオーバーフローする可能性がある。 Rust の場合は checked_mul を使えばオーバーフローを検出できる。使わない場合は 10^18 を A で割ったものとの大小比較などをすれば判定できる。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30188152
今日のコミット。