소수의 배수

Problem link: https://www.acmicpc.net/problem/17436

비트마스킹과 포함배제를 함께 사용해주면 쉽게 풀 수 있다.

문제를 요약하면 곧 주어지는 소수 배열의 배수들의 갯수를 구하는 것이다.

i번째 소수의 배수 집합을 S_i과 같이 표현한다고 하면, 멱집합은 비트마스킹을 통해 표현해줄 수 있다.

• 멱 집합 = n(1 <= n < 2^N): i번 비트가 켜졌다는 것은 S_i를 포함함을 의미한다.

포함배제 원리에서 짝수개 집합의 교집합 크기는 빼주고, 홀수개 집합의 교집합 크기는 더해주었으므로 무지성으로 구현해주면 답을 얻을 수 있다.

#include <iostream>
#include <cstdint>

using namespace std;

const size_t kMaxN = 10;
const int64_t kOne = 1;

int64_t N;
int64_t M;
int64_t PRIMES[kMaxN];

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  cin >> N >> M;
  for (int64_t it = 0; it < N; ++it)
  {
    cin >> PRIMES[it];
  }

  // Solve
  int64_t num_of_mults = 0;
  for (int64_t mask = 1; mask < (kOne << N); ++mask)
  {
    int64_t odd = 0;
    int64_t mul = 1;
    for (int64_t bit = 0; bit < N; ++bit)
    {
      if (mask & (kOne << bit))
      {
        odd = 1 - odd;
        mul *= PRIMES[bit];
      }
    }

    num_of_mults += odd ? M / mul : -M / mul;
  }

  cout << num_of_mults << '\n';

  return 0;
}