Subtask ~1~: ~n = 1~

Số lượng số nguyên dương ~\le Z~ mà chia hết cho ~Y~ nào đó sẽ là ~\lfloor \frac {Z}{Y} \rfloor~.

Vì vậy, kết quả của bài toán là ~\lfloor \frac {x - 1}{a_1} \rfloor~.

Độ phức tạp: ~O~ (~1~).

Subtask ~2~: ~n = 2~

Từ subtask này, ta thấy, các phần tử của mảng ~a~ cần phân biệt. Nếu có một phần tử xuất hiện hai lần trở lên trong mảng ~a~, ta sẽ chỉ giữ lại một mảng.

Từ đây, ta coi như mảng chỉ bao gồm các phần tử phân biệt.

Xuất phát từ ý tưởng bao hàm loại trừ: Kết quả sẽ là (số lượng số chia hết cho ~a_1~) + (số lượng số chia hết cho ~a_2~) - (số lượng số chia hết cho cả hai số).

Vì mảng ~a~ chỉ gồm các số nguyên tố, vậy nên, số lượng số chia hết cho cả ~a_1~ và ~a_2~ là ~a_1 \times a_2~.

Độ phức tạp: ~O~ (~1~).

Subtask ~3~: ~x \le 10^6~

Với subtask này, vì ~x~ nhỏ, ta có thể duyệt mọi số và kiểm tra.

Độ phức tạp: ~O~ (~x \times n~).

Subtask ~4~: ~n \le 15~

Xuất phát từ ý tưởng bao hàm loại trừ như subtask ~2~, nhưng ta sẽ tính toán cho từng tập con.

Độ phức tạp: ~O~ (~2^n \times n~).

Subtask ~5~: ~n \le 25~

Ta sẽ lưu ~p[mask]~ là tích của các ~a_i~ mà có bit thứ ~i~ của ~mask~ bật.

Từ đây, ta có thể tính toán các ~mask~ trong ~O~ (~1~), bằng cách lấy một bit bất kỳ của ~mask~ đang tính, và lấy kết quả từ ~mask~ XOR với bit đó.

Độ phức tạp: ~O~ (~2^n~).

Code mẫu:

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

#define int long long
#define pp pair <int, int>
#define fi first
#define se second
#define yes cout << "YES\n"
#define no cout << "NO\n"

const int N = 1e6 + 9;

int n, x;
int tmp[(1 << 25)];

signed main (){
    ios_base::sync_with_stdio (false);
    cin.tie (NULL);
    cout.tie (NULL);
    if (fopen ("input.txt", "r")){
        freopen ("input.txt", "r", stdin);
        freopen ("output.txt", "w", stdout);
    }
    cin >> n >> x; x--;
    vector <int> a (n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort (a.begin (), a.end ()); a.erase (unique (a.begin (), a.end ()), a.end ());
    n = a.size ();
    int res = 0;
    tmp[0] = 1;
    for (int mask = 1; mask < (1 << n); mask++){
        int idx = __builtin_ctz (mask);
        int y = mask ^ (1 << idx);
        if (tmp[y] == -1) tmp[mask] = -1;
        else if (tmp[y] <= 2e18 / a[idx]) tmp[mask] = tmp[y] * a[idx];
        else tmp[mask] = -1;
        if (tmp[mask] == -1) continue;
        else if (__builtin_popcountll (mask) & 1) res += x / tmp[mask];
        else res -= x / tmp[mask];
    }
    cout << res;
}