この問題を解きました。ネタバレを含むのでご注意ください。
300点問題はいままで書いてなかったんですが、数学的アプローチでACできて大変気持ちがいいのでドヤっておきたいと思います（数学苦手なのでこういう問題が解けると嬉しい）。
整数 A,B,C,D が与えられます。A以上B以下の整数のうち、CでもDでも割り切れないものの個数を求めてください。
問題はシンプルです
制限は
1 <= A <= B <= 10^18 1 <= C, D <= 10^9 入力はすべて整数
となります。
4 9 2 3
入力がこのような場合、4以上9以下の整数のうち2でも3でも割り切れないものの数は2なので、以下が期待される出力になります。
2
与えられる整数が1018と大きすぎるので全部列挙するのは無理なことがわかります。
数学の集合の問題で似たようなやつを解いた記憶があるのでそれを使います。
A以上B以下の整数の集合をA'とします。
A以上B以下の整数のCの倍数の集合をC' とします。
C' = {ceil(A/C)・C, ceil(A/C)+1・C, ... floor(B/C)・C}
A以上B以下の整数のDの倍数の集合をD' とします。
D' = {ceil(A/D)・D, ceil(A/D)+1・D, ... floor(B/D)・D}
A以上B以下の整数の個数からC'とD'の個数を引けばCでもDでも割り切れないものの個数が出てきますが、
これだけだとC'とD'で重複して引いてしまう数が出てくるので、CとDの公倍数でA以上B以下のものの個数を足します。
入力例1の場合だと
A = 4 B = 9 C = 2 D = 3
なので、 C'とD'はそれぞれ以下のようになります。
C' = {2・2, 3・2, 4・2}
D' = {2・3, 3・3}
CとDの最小公倍数は6なので
E' = {1・6}
とすると以下で答えが出ます
// n(A') は B - A + 1 n(A') - n(C') - n(D') + n(E') // => 2
ちなみに最小公倍数は
lcm(a,b) = a*b / gcd(a,b)
で求められます。
提出したコード
