ABC 253 D 勉強メモ

• 包除原理 を活用
  • 包除原理の一般化の部分で、- と + の記号を反転させる + (-1)**n-1 の部分なるほど
  • 今回の問題だけで言えば、集合が A, B のみなので上記はあまり関係無いが...
• std::lcm`` (Python 場合math.lcm```) で最小公倍数が算出できる
  • Python のバージョンによっては math.lcm が存在しない。代わりに a * b // math.gcb(a, b)
  • std::gcb (math.gcb) は最大公約数を求める

コード

#include <bits/stdc++.h>
using namespace std;

/*

[集合]
n(A) = |A| =集合Aの要素数

[包除原理]

|A1 ∨ A2 ∨ ... An|
=   Σ  |Ai|
    i
 -  Σ  |Ai ∧ Aj|
   i<j
 +  Σ  |Ai ∧ Aj ∧ Ak |
  i<j<k

 - ... + (-1)**n-1 | A1 ∧ ... ∧ An |


全ての要素数を足し、余計に足してしまったものを取り除く、イメージ

|A ∨ B| = |A| + |B| - |A ∧ B|
n(A) + n(B) して、n(A ∧ B) を引くことで重複を除外し要素数を計算

|A ∨ B ∨ C| = |A| + |B| + |C| - |A ∧ B| - |B ∧ C| - |C ∧ A| + |A ∧ B ∧ C|

n(A) + n(B) + n(C) して、n(A ∧ B), n(B ∧ C), n(C ∧ A) を引き、余計に引き過ぎた n(A ∧ B ∧ C)
を足して要素数を計算

-/+ を繰り返すので、一般化する際の最後の方で + (-1)**n-1 している。
n が偶数なら (-1)**1 -> -1
n が奇数なら (-1)**0 ->  1

*/
long long calc(long long N, long long x) {
    return x * (1 + floor(N / x)) * floor(N / x) / 2;
}


int main() {
    long long N, A, B;
    cin >> N >> A >> B;

    long long ans = (1 + N) * N / 2;
    cout << ans << endl;

    ans = ans - calc(N, A);
    ans = ans - calc(N, B);
    ans = ans + calc(N, lcm(A, B));
    cout << ans << endl;
}