きろく

特筆すべき記録のまとめ

2019-05-25から1日間の記事一覧

Chokudai SpeedRun 002:J - GCD β

問題 解法 解答 問題 atcoder.jp 解法 最初のペア (A_0, B_0) のどちらかを選ぶかによって作れる GCD の最大値は一意に定まる.具体的には,A_0 を選んだ場合,その次のペアにおいては gcd(A_0, A_1) と gcd(A_0, B_1) のうち大きくなる方を選んだ方が自明に…

Chokudai SpeedRun 002:H - あまり β

問題 解法 解答 問題 atcoder.jp 解法 まず,A = B ならば,答えは -1 になる. そうでないとき,答えは abs(A - B) となる.これは,ある 0 以上の整数 p, q, r を使って,A = pX + r, B = qX + r とあらわすことが出来て,これらから A - B = (p - q)X と…

Chokudai SpeedRun 002:G - GCD α

問題 解法 解答 問題 atcoder.jp 解法 ユークリッドの互除法で各 A_i, B_i の最大公約数は求まる.O(N * log(max(A, B))). 解答 atcoder.jp

Chokudai SpeedRun 002:F - 種類数 α

問題 解法 解答 問題 atcoder.jp 解法 (min(A_i, B_i), max(A_i, B_i)) をペアとし,std::set に追加していく.最終的な set のサイズが答えになる.O(NlogN). 解答 atcoder.jp