Hướng giải của Bội số trong đoạn

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Ý tưởng: Dùng nguyên lý bù trừ (inclusion-exclusion). Duyệt qua tất cả 2^K tập con của các số nguyên tố. Với mỗi tập con, tính tích các số nguyên tố trong tập đó (nếu tích ≤ N). Nếu tập con lẻ, cộng N/tích; nếu chẵn, trừ N/tích.

Độ phức tạp: O(2^K) thời gian, O(1) bộ nhớ.

C++

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll k, n;
    cin >> k >> n;
    vector<ll> p(k);
    for (auto &x : p) cin >> x;
    ll ans = 0;
    for (int mask = 1; mask < (1 << k); mask++) {
        ll prod = 1;
        int bits = 0;
        bool ok = true;
        for (int i = 0; i < k; i++) {
            if (mask >> i & 1) {
                bits++;
                if (prod > n / p[i]) {
                    ok = false;
                    break;
                }
                prod *= p[i];
            }
        }
        if (!ok) continue;
        if (bits & 1) ans += n / prod;
        else ans -= n / prod;
    }
    cout << ans << "\n";
    return 0;
}

Python

python
k, n = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
for mask in range(1, 1 << k):
    prod = 1
    bits = 0
    ok = True
    for i in range(k):
        if mask >> i & 1:
            bits += 1
            if prod > n // p[i]:
                ok = False
                break
            prod *= p[i]
    if not ok:
        continue
    if bits & 1:
        ans += n // prod
    else:
        ans -= n // prod
print(ans)

Nhận xét

Không có ý kiến tại thời điểm này.