包除原理（Divisors）

問題

1 以上 N 以下の整数のうち、3,5のいずれかで割り切れるものは何個ありますか。

[制約]
🔹1≦N≦1012

解き方・ソースコード

この問題は包除原理を使うと簡単に解くことができます。

包除原理は要素数に関する等式で、集合P,Q の和集合の要素数は下記の式で表せるというものです。

[集合P,Qの和集合の要素数]=[集合Pの要素数]+[集合Qの要素数]−[集合P,Qの共通部分の要素数]

---

包除原理を、今回の問題に当てはまると次のようになります。

[3の倍数の個数]+[5の倍数の個数]−[15の倍数の個数]

また、1 以上 N 以下の整数のうち x の倍数の個数を求めるには N/x で求めることができます。

[Google Colaboratory]

#-------- 入力例１ ----------
N = 10
#-------- 入力例２ ----------
# N = 30
#-------- 入力例３ ----------
# N = 100000000000
#----------------------------
A1 = (N //  3) # 3 で割り切れるものの個数
A2 = (N //  5) # 5 で割り切れるものの個数
A3 = (N // 15) # 3, 5 両方で割り切れるもの（= 15 の倍数）の個数
print('解：', A1 + A2 - A3)

[実行結果（入力例１）]

解： 5

[実行結果（入力例２）]

解： 14

[実行結果（入力例３）]

解： 46666666667