Hướng giải của Chia hết 2

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.

Công Thức Tổng Quát

Giả sử tập các số nguyên tố cho trước là

\[ P = \{P_1, P_2, \dots, P_n\}, \]

với \(n\) số nguyên tố. Để đếm số các số trong khoảng \([L, R]\) chia hết duy nhất cho đúng 1 số nguyên tố trong \(P\),

Ta định nghĩa hàm:

\[ F(X) = \sum_{\emptyset \neq I \subseteq \{1,2,\dots,n\}} (-1)^{|I|-1}\,|I|\cdot \left\lfloor \frac{X}{\displaystyle \prod_{i \in I} P_i} \right\rfloor, \]

trong đó:

  • \(I\) chạy qua tất cả các tập con không rỗng của chỉ số \(\{1,2,\dots,n\}\).
  • \(|I|\) là số phần tử của tập \(I\).
  • \(\prod_{i\in I} P_i\) là tích các số nguyên tố thuộc tập con \(I\).
  • \(\left\lfloor \frac{X}{\prod_{i\in I} P_i} \right\rfloor\) đếm số các số từ 1 đến \(X\) chia hết cho tích đó.

Sau đó, đáp án cần tìm (số các số trong khoảng \([L, R]\) chia hết duy nhất cho đúng 1 số nguyên tố trong \(P\)) được tính bằng hiệu:

\[ \text{Đáp án} = F(R) - F(L-1). \]

Giải Thích

  • Tính \(\left\lfloor \frac{X}{\prod_{i \in I} P_i} \right\rfloor\):
    Đây là số các số \(x\) (với \(1 \le x \le X\)) chia hết cho tích của các số nguyên tố được chọn trong tập con \(I\).

  • Hệ số \((-1)^{|I|-1}\):
    Áp dụng nguyên lý bù trừ (inclusion–exclusion) để hiệu chỉnh việc đếm chồng, đảm bảo rằng các số \(x\) chia hết cho nhiều hơn 1 số nguyên tố trong tập \(P\) bị triệt tiêu các đóng góp chồng lên nhau.

  • Trọng số \(|I|\):
    Nhân với số lượng phần tử trong tập con giúp gán trọng số cho từng số nguyên tố đóng góp vào số \(x\) được đếm. Điều này đảm bảo rằng:

    • Nếu \(x\) chỉ chia hết cho 1 số nguyên tố thì đóng góp là \(+1\).
    • Nếu \(x\) chia hết cho từ 2 số trở lên thì tổng các đóng góp theo quy tắc bù trừ sẽ triệt tiêu nhau.

Cuối cùng, ta lấy hiệu giữa \(F(R)\) và \(F(L-1)\) để có số các số trong khoảng \([L, R]\) thoả mãn yêu cầu của đề bài.

#include <bits/stdc++.h>
#define sz(a) (a).size()
#define ll long long
#define fi first
#define se second
#define str to_string
#define pi pair<int,int>
#define pii pair<int,pair<int,int>
#define MASK(i) (1LL << (i))
#define BIT(x,i) (((x) >> (i)) & 1)
#define set_on(x,i) ((x) | mask(i))
#define set_off(x,i) ((x) & ~mask(i))
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)

using namespace std;

const int maxN = 20+5;
const int oo = 1e9+7;
const int N = 1e6;

int n;
vector <int> a;
ll l, r;

ll solve (ll id) {
    ll ans = 0;
    for (int mask = 1;mask < (1<<n); mask++) {
        ll mul = 1;
        bool grt = 0;
        for (int i = 0;i < n; i++) {
            if (BIT(mask, i)) {
                if (mul > id / a[i]) grt = 1;
                mul *= a[i];
            }
        }
        if (grt) continue;
        int bits = __builtin_popcount(mask);
        if (bits & 1) ans += bits * (id/mul);
        else ans -= bits*(id/mul);
    }
    return ans;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n >> l >> r;
    for (int i = 0;i < n; i++) {
        int x;
        cin >> x;
        a.push_back(x);
    }
    cout << solve(r) - solve(l-1) << "\n";

    cerr << "Time elapsed: " << TIME << "s\n";
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

// Hàm đếm số bội của x trong khoảng [L, R]
unsigned long long countMultiples(unsigned long long L, unsigned long long R, unsigned long long x) {
    if(x == 0) return 0;
    return R / x - (L - 1) / x;
}

// Hàm DFS liệt kê các tập con của các số nguyên tố khác (ngoại trừ P_i)
// Các tham số:
// - others: vector chứa các số nguyên tố còn lại (không bao gồm P_i)
// - pos: vị trí hiện tại duyệt trong vector others
// - current: giá trị tích hiện tại (đã nhân với P_i ban đầu)
// - cnt: số lượng phần tử đã chọn trong tập con hiện tại (để xác định dấu hiệu ±)
// - L, R: khoảng cho đề bài
// - sum: biến tham chiếu cập nhật tổng hiệu chỉnh theo inclusion-exclusion
void dfs(const vector<unsigned long long>& others, int pos, unsigned long long current, int cnt,
         unsigned long long R, unsigned long long L, unsigned long long &sum) {
    for (int i = pos; i < others.size(); i++) {
        // Kiểm tra nếu nhân sẽ vượt R, do đó không cần duyệt tiếp (đảm bảo current * others[i] <= R)
        if (current > R / others[i]) continue; 
        unsigned long long newProd = current * others[i];
        // Khi thêm 1 số mới, số lượng phần tử trong tập con tăng lên (cnt + 1)
        // Nếu (cnt+1) lẻ => dấu âm, nếu chẵn => dấu dương
        if ((cnt + 1) % 2 == 1) {
            sum -= countMultiples(L, R, newProd);
        } else {
            sum += countMultiples(L, R, newProd);
        }
        dfs(others, i + 1, newProd, cnt + 1, R, L, sum);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    unsigned long long L, R;
    cin >> n >> L >> R;
    vector<unsigned long long> primes(n);
    for (int i = 0; i < n; i++){
        cin >> primes[i];
    }

    unsigned long long ans = 0;
    // Với mỗi số nguyên tố P_i, ta tính số các số chia hết duy nhất cho P_i
    for (int i = 0; i < n; i++) {
        // Số các số chia hết cho P_i
        unsigned long long res_i = countMultiples(L, R, primes[i]);

        // Chuẩn bị vector chứa các số nguyên tố khác (ngoại trừ P_i)
        vector<unsigned long long> others;
        for (int j = 0; j < n; j++) {
            if(j != i)
                others.push_back(primes[j]);
        }

        // Sử dụng DFS để tính hiệu chỉnh theo inclusion-exclusion:
        // Ta sẽ trừ các số chia hết cho P_i và 1 số khác, cộng lại với trường hợp nhân 2 số khác, trừ lại với nhân 3 số khác, v.v...
        unsigned long long sub = 0;
        dfs(others, 0, primes[i], 0, R, L, sub);

        // Tổng theo công thức: F(P_i) = f(P_i) + (các hiệu chỉnh từ DFS)
        res_i += sub;
        ans += res_i;
    }

    cout << ans << "\n";
    return 0;
}

Nhận xét

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