包除原理：重なりを引き戻す

Aに属する数とBに属する数を足すと、両方に属する数を二度数えます。共通部分を引いて補正します。

言語：Python / 計算量：2集合の例 O(log min(A,B))

前提：最大公約数とユークリッドの互除法

考え方

  1. 2集合なら
  2. A∪B
  3. =
  4. A
  5. +
  6. B
  7. -
  8. A∩B
  9. 。
  10. 3集合なら各集合を足し、2集合の共通部分を引き、3集合の共通部分を足します。
  11. 倍数の共通部分は最小公倍数の倍数です。

具体例

1..10で2または3の倍数は、5個+3個-6の倍数1個=7個。

実装

from math import lcm
n=10;a=2;b=3
print(n//a+n//b-n//lcm(a,b))

注意する条件

集合の数Kが増えると部分集合は2^K。重なりの計算コストも含めて見積もります。

確認問題

1..10で2または3の倍数は何個？

解答と理由

7

2,3,4,6,8,9,10です。

実装課題

N A B（1≤N,A,B≤10^18）。1..N の中でAまたはBで割り切れる数の個数。

入力:
10 2 3
出力:
7
参考実装
from math import gcd
n,a,b=map(int,input().split());l=a//gcd(a,b)*b
print(n//a+n//b-n//l)

読了の記録・下書き・メモへ