数学アルゴ本 068 - Number of Multiples 2 (1Q)

包除原理の基本！

• 問題へのリンク

問題概要

1 以上 以下の整数のうち、 のいずれかで割り切れるものの個数を求めよ。

制約

• 
• 
• 

考えたこと

包除原理の超典型問題。たとえば のときは、次のように考えればよい。

(V[0] で割り切れる個数)
+ (V[1] で割り切れる個数)
+ (V[2] で割り切れる個数)
- (V[0], V[1] で割り切れる個数)
- (V[0], V[2] で割り切れる個数)
- (V[1], V[2] で割り切れる個数)
+ (V[0], V[1], V[2] で割り切れる個数)

より一般に、 個の場合には

(V[0], ..., V[K-1] のうち少なくとも 1 個で割り切れる個数)
- (V[0], ..., V[K-1] のうち少なくとも 2 個で割り切れる個数)
+ (V[0], ..., V[K-1] のうち少なくとも 3 個で割り切れる個数)
- (V[0], ..., V[K-1] のうち少なくとも 4 個で割り切れる個数)
+ ...

を計算すればよい。計算量は となる。

コード

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

long long lcm(long long a, long long b) {
    long long g = gcd(a, b);
    return a / g * b;
}

int main() {
    long long N, K;
    cin >> N >> K;
    vector<long long> V(K);
    for (int i = 0; i < K; ++i) cin >> V[i];
    
    long long res = 0;
    for (int S = 1; S < (1 << K); ++S) {
        long long val = 1;
        for (int i = 0; i < K; ++i) {
            if (S & (1 << i)) val = lcm(val, V[i]);
        }
        
        if (__builtin_popcount(S) % 2 == 1) res += N / val;
        else res -= N / val;
    }
    cout << res << endl;
}