包除原理（Divisors）

問題

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

[制約]
🔹$ 1 \leqq N \leqq 10^{12} $

解き方・ソースコード

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

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

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

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

$ [3の倍数の個数] + [5の倍数の個数] - [15の倍数の個数] $

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

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
#-------- 入力例１ ----------
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