olpkhhue22 - Đếm dãy số
Xem PDF
Điểm:
2800 (p)
Thời gian:
5.5s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho số nguyên dương \(n\) cùng hai dãy số nguyên dương \(l_1, l_2, \ldots, l_n\) và \(r_1, r_2, \ldots, r_n\). Bạn cần đếm số dãy số nguyên \((x_1, x_2, \ldots, x_n)\) sao cho:
- \(l_i \leq x_i \leq r_i\) với mọi \(1 \leq i \leq n\).
- \(lcm(x_1, x_2, \ldots, x_n) = \max(x_1, x_2, \ldots, x_n)\)
Ở đây, \(lcm(x_1, x_2, \ldots, x_n)\) là số nguyên dương \(X\) nhỏ nhất sao cho \(x_i\) là ước của \(X\) với mọi \(1 \leq i \leq n\); và \(\max(x_1, x_2, \ldots, x_n)\) là giá trị lớn nhất của dãy số này.
Do kết quả có thể rất lớn, bạn chỉ cần in ra kết quả theo modulo \(998244353\).
Input
Dòng đầu tiên chứa số nguyên \(\theta\) \((1 \leq \theta \leq 5)\) là số bộ dữ liệu. Tiếp theo là các bộ dữ liệu lần lượt được mô tả theo khuôn dạng sau:
- Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 100000)\).
- Trong \(n\) dòng còn lại, dòng thứ \(i\) chứa hai số nguyên \(l_i\) và \(r_i\) \((1 \leq l_i^{l_i} \leq r_i \leq 900000)\).
Output
- Với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên duy nhất là số dãy số thỏa mãn các yêu cầu ở trên. Do kết quả có thể rất lớn, bạn chỉ cần in ra phần dư của số dãy đếm được khi chia cho \(998244353\).
Example
Test 1
Input
2
3
2 4
2 5
1 3
2
1 2
2 4Output
10
5
Bình luận
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
bài khó quá
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.