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

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

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

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;

}

1 phản hồi

-1

PY1BTranGiaKhang 7:47 p.m. 18 Tháng 11, 2023

hơi xúi dại một tí ai làm thì làm ko là thì thôi

-9

PY1BTranGiaKhang 7:41 p.m. 18 Tháng 11, 2023 ← đã chỉnh sửa →

copy code trong hướng dẫn câu cuối

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

0

PY1F04_phan_nhat_binh 5:36 p.m. 12 Tháng 11, 2023

cho em xin code gợi ý với

-1

kid123456789 10:09 p.m. 12 Tháng 10, 2023

bài này làm tổ hợp dc mà