「A 以上 B 以下の整数のうち〜を満たすものの個数を求めよ」という問題では
- (B 以下の整数のうちの〜を満たすものの個数) から
- (A-1 以下の整数のうちの〜を満たすものの個数) を引く
とすると、すごくやりやすい!!!!!
このテクニックは大昔の topcoder ではよくあった。最近だとこれとか。
問題概要
以上 以下の整数のうち、 の倍数でも の倍数でもないものの個数を求めよ。
考えたこと
以下の整数のうち、 の倍数でも の倍数でもないものの個数が求められればよい。これは
- (全体) + (C の倍数の個数) + (D の倍数の個数) - (C の倍数でも D の倍数でもあるものの個数)
によって求めることができる。いわゆる高校数学で懐かしいベン図というやつ。
(全体)
これは 以下の整数だから 個
(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 は次のようにして求めることができる。
- C と D の最大公約数 G をユークリッドの互除法によって求める。
- L = C / G * D となる
ここで、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; }