けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 131 C - Anti-Division (300 点)

「A 以上 B 以下の整数のうち〜を満たすものの個数を求めよ」という問題では

  • (B 以下の整数のうちの〜を満たすものの個数) から
  • (A-1 以下の整数のうちの〜を満たすものの個数) を引く

とすると、すごくやりやすい!!!!!
このテクニックは大昔の topcoder ではよくあった。最近だとこれとか。

drken1215.hatenablog.com

問題へのリンク

問題概要

 A 以上  B 以下の整数のうち、 C の倍数でも  D の倍数でもないものの個数を求めよ。

考えたこと

 N 以下の整数のうち、 C の倍数でも  D の倍数でもないものの個数が求められればよい。これは

- (全体)
+ (C の倍数の個数)
+ (D の倍数の個数)
- (C の倍数でも D の倍数でもあるものの個数)

によって求めることができる。いわゆる高校数学で懐かしいベン図というやつ。

(全体)

これは  N 以下の整数だから  N

(C の倍数の個数)

これは  N C で割った商 (あまりを切り捨て) になる。たとえば 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 のうち、3 の倍数は

10 ÷ 3 = 3 ... 1

なので、3 個になる。C++ プログラミングでは

N / C

と非常に簡単に書ける。

(D の倍数の個数)

同様に、N/D 個

(C の倍数でも、D の倍数でもあるやつの個数)

「C の倍数でも、D の倍数でもある」というのは C でも D でも割り切れるということ。

つまり、C と D の最小公倍数で割り切れるということ。C と D の最小公倍数 L は次のようにして求めることができる。

ここで、L = C * D / G としてもよいのだけど、C * D でのオーバーフローが微妙に怖くて C / G * D にすることが多い。

まとめ

N 以下の整数のうち、C でも D でも割り切れない個数は

  • N - N/C - N/D + N/L

である

#include <iostream>
using namespace std;

long long GCD(long long x, long long y) { return y ? GCD(y, x%y) : x; }
long long num(long long n, long long c, long long d) {
    long long G = GCD(c, d);
    long long L = c / G * d;
    return n - n / c - n / d + n / L;
}

int main() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << num(b, c, d) - num(a-1, c, d) << endl;
}