ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC131 C - Anti-Division

問題文
提出コード

解法

ベン図を見ると見通しが良くなります。
(X以下のCでもDでも割り切れない数)を求めるには、
全体のXから、(X以下のCで割り切れる数)+(X以下のDで割り切れる数)を引き、(X以下のCでもDでも割り切れる数)を足せばよいです。
f:id:emtubasa:20190626152957p:plain
これが全体の図です。

f:id:emtubasa:20190626154706p:plain
という式になります。
(A以上B以下のPで割り切れる数)、というのは
(B以下のPで割り切れる数)から(A未満のPで割り切れる数)を引けばいいので、
答えをつらつらと記述すると、
B-(A-1)-(B以下のCで割り切れる数)+(A未満のCで割り切れる数)
-(B以下のDで割り切れる数)+(A未満のDで割り切れる数)
+(B以下のCでもDでも割り切れる数)-(A未満のCでもDでも割り切れる数)
となります。
(CでもDでも割り切れる数)というのは、LCM(C,D)で割り切れる数のことです。
(X以下のPで割り切れる数)=X/P (切り捨て)
なので、あとはこれを計算すれば答えを求めることができます。

感想

いろんな典型が詰まった問題だと思います。
包除原理っぽいことも、要素が少なければベン図で事足りるのでスッキリします。