Zenn
Open2

包除原理 調べてみたこと

math
競プロ
hidehic0hidehic0

用途

1からN以下の整数のうち
AまたはBで割り切れる数または割り切れない数

求め方

割り切れる数

\lfloor \frac{N}{A} \rfloor + \lfloor \frac{N}{B} \rfloor - \lfloor \frac{N}{\operatorname{lcm}(A,B)} \rfloor

python
import math
N//A + N//B - N // math.lcm(A,B)

割り切れない数

N - (\lfloor \frac{N}{A} \rfloor + \lfloor \frac{N}{B} \rfloor) + \lfloor \frac{N}{\operatorname{lcm}(A,B)} \rfloor

python
import math
N//A + N//B - N // math.lcm(A,B)

実際もっとカッコつけてます(心配性だから)