[AtCoder] ABC 131 C – Anti-Division

問題

方針

範囲内の \( C \) かつ \( B \) で割り切れるものの数を求めて、全体から引けばよいです。どのように求めるかというと、範囲内の \( C\) と \(D \) の倍数の個数から \( C, D \) の最小公倍数の個数を引けばよいです。

区間に存在する \( g \) 倍数の個数

区間 \([l, r] \) に \( g \) の倍数が含まれる個数 \( k \) は、

\[ k = \lfloor \dfrac{r + g}{g}\rfloor – \lfloor \dfrac{l +g – 1}{g}\rfloor \]

と表すことができます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll gcd(ll m, ll n) {
  if (n == 0) return m;
  else return gcd(n, m % n);
}

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll A, B, C, D;
  cin >> A >> B >> C >> D;
  ll ans = B - A + 1;
  ll kc = (B + C) / C - (A + C - 1) / C;
  ll kd = (B + D) / D - (A + D - 1) / D;
  ll g = lcm(C, D);
  ll kg = (B + g) / g - (A + g - 1) / g;
  ans = ans - kc - kd + kg;
  cout << ans << "\n";
  return 0;
}