Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

包除原理(Divisors)

問題

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

[制約]
🔹1N1012

解き方・ソースコード

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

包除原理は要素数に関する等式で、集合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
#-------- 入力例1 ----------
N = 10
#-------- 入力例2 ----------
# N = 30
#-------- 入力例3 ----------
# N = 100000000000
#----------------------------
A1 = (N // 3) # 3 で割り切れるものの個数
A2 = (N // 5) # 5 で割り切れるものの個数
A3 = (N // 15) # 3, 5 両方で割り切れるもの(= 15 の倍数)の個数
print('解:', A1 + A2 - A3)

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

解: 5

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

解: 14

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

解: 46666666667