記憶

思考の掃きだめ、雑記

ABC131 C問題

 

 

問題

 

atcoder.jp

解答

数学の基本問題とかでよく見かけた感じの問題でした

割り切れないものの数をいきなり求めるのは難しいので、全体から割り切れるものの数を引く方向で攻めます。

 

この問題で考える範囲はA~BのB-A+1個です

 

まず、この範囲でCでもDでも割り切れるものを求めます

言い換えると、この範囲の数で、CもしくはDで割り切れるものの数を求めるということです。

X以下の正の整数のなかでYで割り切れるものの数はX/Yなので、これを何度も使います

 

以下簡単に

 

A-Bの中で(Cで割れるものの数)+(Dで割れるものの数)-(CでもDでも割れるものの数)を出せばOK・・・(※)

CでもDでも割れる物の数は、CとDの最小公倍数で割り切れる物の数と等しいので、それを利用します

 

先ほどの(※)をA-B+1から引いて終わりです

atcoder.jp

 

競プロ関連は初めて書きました

まだまだ勉強不足でわからないことばかりなのでいろいろご指導お願いします!