包除原理②(Divisors)

問題

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

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

解き方・ソースコード

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

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

 [集合P,Q,Rの和集合の要素数] = [集合Pの要素数] + [集合Qの要素数] + [集合Rの要素数] 

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

                            - [集合Q,Rの共通部分の要素数] 

                            - [集合P,Rの共通部分の要素数] 

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

集合が3つ以上になるとプラスするかマイナスするか少々分かりにくくなるかもしれませんが、重なりが奇数個の場合はプラス、重なりが偶数個の場合はマイナスと考えると分かりやすくなります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#-------- 入力例1 ----------
N = 10
#-------- 入力例2 ----------
# N = 30
#-------- 入力例3 ----------
# N = 100000000000
#----------------------------
# 計算
A1 = (N // 3); # 3 で割り切れるものの個数
A2 = (N // 5); # 5 で割り切れるものの個数
A3 = (N // 7); # 5 で割り切れるものの個数
A4 = (N // 15); # 3, 5 で割り切れるもの(= 15 の倍数)の個数
A5 = (N // 21); # 3, 7 で割り切れるもの(= 21 の倍数)の個数
A6 = (N // 35); # 5, 7 で割り切れるもの(= 35 の倍数)の個数
A7 = (N // 105); # 3, 5, 7 で割り切れるもの(= 105 の倍数)の個数

print('解:', A1 + A2 + A3 - A4 - A5 - A6 + A7)

[実行結果(入力例1)]

解: 6

[実行結果(入力例2)]

解: 17

[実行結果(入力例3)]

解: 54285714286