F - Fizzbuzz expansion

例えば $N=3$ の時、

($A_1 A_2 A_3$ のどれかで割れるもの総数)=
$A_1$ で割り切れる数字
+$A_2$ で割り切れる数字
+$A_3$ で割り切れる数字
−$A_1$、$A_2$ 双方で割り切れる数字
−$A_1$、$A_3$ 双方で割り切れる数字
−$A_1$、$A_3$ 双方で入割り切れる数字
+$A_1$、$A_2$、$A_3$ のすべてで割り切れる数字
となります。

$2^N$ 通りを全探索することを考えます。このとき、以下の問題が解ければ元の問題も解けることになります。

$A_1 A_2 \cdots A_k$のすべてで割り切れる数字は何個あるか？

この場合の答えは、$\lfloor\tfrac{X}{LCM(A_1, A_2 \cdots A_k)}\rfloor$で求まります。(Fizzbuzzの典型です)

$2^N$ 通り全てについて包除原理に従って適切に足し引きしていくことで、この問題を $O(N^2)$ で解くことが出来ます。

類題

ABC246 F - typewrite

import math

def GCD(a,b):
    return math.gcd(a,b)

def LCM(a,b):
    return a*b//GCD(a,b)

def f(A):
    p = 1
    for a in A:
        p = LCM(a,p)
    return p

n, x = map(int,input().split())
A = list(map(int,input().split()))
    
ans = 0
for i in range(1,1<<n):
    B = []
    for j in range(n):
        if(i>>j & 1):
            B.append(A[j])

    if(len(B)%2==1):
        ans += (x//f(B))
    else:
        ans -= (x//f(B))
        
print(ans)

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

int main(){
    
    ll n, x;
    cin >> n >> x;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    ll ans = 0;
    for (int i = 1; i < (1 << n); i++) {

        ll k = 1, cnt = 0;
        bool overflow = false;

        for (int j = 0; j < n; j++) {
            if ((i >> j) & 1) {
                if (x / (k / gcd(k, a[j])) / a[j] == 0) {
                    overflow = true;
                    break;
                }
                k *= a[j] / gcd(k, a[j]);
                cnt++;
            }
        }
        if (overflow) continue;

        ans += (cnt % 2 == 1 ? 1 : -1) * x / k;
    }

    cout << ans << endl;
}