Anti-Division [AtCoder Beginner Contest 131 C]

https://atcoder.jp/contests/abc131/tasks/abc131_c

解説

https://atcoder.jp/contests/abc131/submissions/6076233

常套テクとして「区間[a,b]の個数は区間[1,b]の個数-区間[1,a)の個数」というのがある。
（今日の北陸アルゴリズム勉強会でtorusさんが言ってたやつ早速出た）
f(x) := 区間[1,x]の整数のうち、CでもDでも割り切れないものの個数
これを作ることができれば、f(B)-(A-1)が答え。
　
CでもDでも割り切れないというのが若干厄介。
割り切れないというのが厄介なので、「全部-CかDで割り切れる」という風に考えよう。
C=Dであれば、Cで割り切れる個数を引けばいい。
そうでないなら、「CかDで割り切れる=Cで割り切れる+Dで割り切れる+CでもDでも割り切れる」なので、
それぞれ計算をして、足し引きすればいい。

ll A, B, C, D;
//---------------------------------------------------------------------------------------------------
ll f(ll x) {
	if (x == 0) return 0;

	ll lc = lcm(C, D);
	return x - (countMultiple(x, C, 0) + countMultiple(x, D, 0) - countMultiple(x, lc, 0));
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> A >> B >> C >> D;
	cout << f(B) - f(A - 1) << endl;
}