2022-03-04 アルゴリズムと数学 演習問題集 068 - Number of Multiples 2 を解いた
アルゴリズムと数学 演習問題集 068 - Number of Multiples 2 を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_be
包除原理の問題。ヒントのビット全探索は制約 K <= 10 から K を対象にしたものだと推測できる。 K のビット全探索ですべての V_i の組み合わせを処理する。
1 以上 N 以下の整数における x の倍数の個数は N / x (切り捨て) で求められる。
V_i についてのこれらの個数の和を取ると V から 2 つを選んだときの個数などを足しすぎてしまう。包除原理に従って足しすぎた分を引き、引きすぎた分を足す……。これを繰り返していく。つまり奇数個のとき足して偶数個のとき引けば良い。
2 個の正の整数の倍数は最小公倍数を使う。最小公倍数は lcm(a, b) = a * b / gcd(a, b) で求められる。最大公約数は gcd(a, b) = if a == 0 then b else gcd(b, a % m) で求められる。 3 個以上のときは最小公倍数と次の値との最小公倍数を求めれば良い lcm(lcm(a, b), c) 。
先に書いたとおりビット全探索ですべての V_i の組み合わせに対してこれを計算しても K <= 10 なら間に合う。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29842175
ひな人形を片付けた (2022-03-01) 。
『ドラえもん のび太の宇宙開拓史』を観た。
今日のコミット。