PVHOI3 - Bài 5: Đề bài siêu ngắn

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
Flower_On_Stone , skyvn97
Dạng bài
Điểm: 2300 (p) Thời gian: 0.25s Bộ nhớ: 1G Input: DEBAISIEUNGAN.inp Output: DEBAISIEUNGAN.out

Cho bốn số nguyên dương \(n, k, a\) và \(b\). Hãy đếm số dãy số nguyên dương \(x_{1}, x_{2}, \ldots, x_{n}\) sao cho:

  • Với mọi \(1 \leq i \leq n, a \leq x_{i} \leq b\).
  • Bội số chung nhỏ nhất của các số \(x_{1}, x_{2}, \ldots, x_{n}\) chia hết cho \(k\).

Do số lượng dãy có thể rất lớn, bạn chỉ cần in ra kết quả theo modulo \(998244353\).

Input

  • Gồm một dòng duy nhất chứa bốn số nguyên \(n, k, a\) và \(b\) \((1 \leq n \leq 227,1 \leq k \leq 10^{14}, 1 \leq a \leq b \leq 10^{14})\).

Output

  • Gồm một số nguyên duy nhất là kết quả của bài toán nêu trên theo modulo \(998244353\).

Scoring

  • Subtask \(1\) (\(7\) điểm): \(k = 1\)
  • Subtask \(2\) (\(8\) điểm): \(n \leq 5, b \leq 30\) và \(k \leq 30\).
  • Subtask \(3\) (\(9\) điểm): \(n \leq 5\) và \(b - a \leq 30\)
  • Subtask \(4\) (\(10\) điểm): \(k\) là số nguyên tố
  • Subtask \(5\) (\(16\) điểm): \(b \leq 10^{7}\) và \(k \leq 10^{7}\)
  • Subtask \(6\) (\(20\) điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
2 6 10 14
Output 
9
Note

Trong ví dụ thứ nhất, các dãy số thoả mãn là \((10, 12)\), \((11, 12)\), \((12, 10)\), \((12, 11)\), \((12, 12)\), \((12, 13)\), \((12, 14)\), \((13, 12)\), \((14, 12)\).

Test 2

Input 
3 5 7 9
Output 
0
Note

Trong ví dụ thứ hai, do \(7 \leq x_{i} \leq 9\) với mọi \(1 \leq i \leq n = 3\) nên chắc chắn bội số chung nhỏ nhất của các số này không thể chia hết cho \(k = 5\).

Bình luận


  • -2
    kingofgame    12:21 a.m. 29 Tháng 5, 2024

    include <iostream>

    include <fstream>

    include <vector>

    using namespace std;

    const int mod = 998244353;
    const int N = 1e7 + 5;
    vector <long long> p;

    int f[1 << 15];
    int dp[1 << 15];
    long long cnt[1 << 15];
    int mask[N];

    int bit(int x) {
    return (1 << x);
    }

    int getbit(int x, int i) {
    return (x >> i) & 1;
    }

    void add(int &a, int b) {
    a += b;
    if (a >= mod)
    a -= mod;
    }

    int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen("DEBAISIEUNGAN.inp","r",stdin);
    freopen("DEBAISIEUNGAN.out","w",stdout);
    long long n, k, a, b;
    cin >> n >> k >> a >> b;
    for (int i = 2; (long long) i * i <= k; i++) {
    if (k % i == 0) {
    long long x = 1;
    while (k % i == 0) {
    k /= i;
    x *= i;
    }
    p.push_back(x);
    }
    }
    if (k > 1)
    p.push_back(k);

    int sz = p.size();
for (int mask = 0; mask < bit(sz); mask++) {
    long long x = 1;
    for (int j = 0; j < sz; j++) 
        if (getbit(mask, j)) 
            x *= p[j];

    cnt[mask] = (b / x) - ((a - 1) / x);
}

for (int mask = bit(sz) - 1; mask > 0; mask--) {
    for (int s = (mask - 1) & mask;; s = (s - 1) & mask) {
        cnt[s] -= cnt[mask];
        if (s == 0)
            break;
    }
}

for (int mask = 0; mask < bit(sz); mask++)
    cnt[mask] %= mod;

for (int mask = 0; mask < bit(sz); mask++) {
    add(dp[mask], cnt[mask]);
    if (mask == 0)
        continue;
    for (int s = (mask - 1) & mask;; s = (s - 1) & mask) {
        add(dp[mask], cnt[s]);
        if (s == 0)
            break;
    }
}

for (int mask = 0; mask < bit(sz); mask++) {
    f[mask] = 1;
    for (int i = 1; i <= n; i++) 
        f[mask] = (long long) f[mask] * dp[mask] % mod;
}

for (int mask = 1; mask < bit(sz); mask++)
for (int s = (mask - 1) & mask;; s = (s - 1) & mask) {
    add(f[mask], mod - f[s]);
    if (s == 0)
        break;
}

cout << f[bit(sz) - 1];

return 0;

    }

    • 4 bình luận nữa