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

Xem PDF




Tác giả:
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\)\(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\)\(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\)\(k \leq 30\).
  • Subtask \(3\) (\(9\) điểm): \(n \leq 5\)\(b - a \leq 30\)
  • Subtask \(4\) (\(10\) điểm): \(k\) là số nguyên tố
  • Subtask \(5\) (\(16\) điểm): \(b \leq 10^{7}\)\(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


  • 0
    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


    • -3
      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


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

        cho em xin code gợi ý với


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

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