問題
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]
1 | #-------- 入力例1 ---------- |
[実行結果(入力例1)]
解: 5
[実行結果(入力例2)]
解: 14
[実行結果(入力例3)]
解: 46666666667