[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; }
ディスカッション
コメント一覧
まだ、コメントがありません