BOJ 14848 - 정수 게임

BOJ 14848 - 정수 게임

포함 배제의 원리 기본 문제이다. 가뿐히 풀어주면 된다.

void solve() {
   int n, k;
   cin >> n >> k;
   vi a(k);
   fv(a);
   ll ans = 0;
   for (int m = 0; m < (1 << k); m++) {
      int cnt = __builtin_popcount(m);
      ll L = 1;
      for (int i = 0; i < k; i++) {
         if (m & (1 << i)) {
            L = lcm(L, a[i]);
            if (L > n) break;
         }
      }
      ans += ll(n / L) * (cnt % 2 ? -1 : 1);
   }
   cout << ans;
}