CTT 2026 - Three
Xem PDF
Điểm:
2700 (p)
Thời gian:
8.0s
Bộ nhớ:
1G
Input:
bàn phím
Output:
màn hình
Có \(n\) ô, được đánh số từ \(0\) đến \(n-1\). Ban đầu, mọi ô đều màu trắng.
Ta thực hiện ba lần tô màu. Lần thứ \(i\) (\(1\le i\le 3\)) cho hai số \(a_i,b_i\) thỏa mãn \(0\le b_i<a_i\), rồi tô đen mọi ô \(x\) thỏa mãn
\[
x\bmod a_i=b_i.
\]
Sau ba lần tô, hãy đếm số đoạn khác nhau \([l,r]\) thỏa mãn \(0\le l\le r<n\) mà tất cả các ô từ \(l\) đến \(r\) vẫn màu trắng. Do kết quả có thể rất lớn, hãy in kết quả theo modulo \(998\,244\,353\).
Dữ liệu vào
- Dòng đầu chứa số nguyên dương \(n\).
- Dòng thứ \(i+1\) (\(1\le i\le 3\)) chứa hai số nguyên không âm \(a_i,b_i\).
Dữ liệu ra
In một số nguyên không âm: số đoạn thỏa mãn, lấy modulo \(998\,244\,353\).
Ràng buộc
\[
1\le n\le 10^{13}
\]
\[
0\le b_i<a_i\le 2n\qquad (1\le i\le 3)
\]
Chấm điểm
| Phần | Điểm | Giới hạn thêm |
|---|---|---|
| 1 | 5 | \(n\le 10^6\) |
| 2 | 25 | \(n\le 10^{13}\); \(a_3>b_3\ge n\) |
| 3 | 5 | \(n\le 10^{13}\); \(\lfloor n/a_1\rfloor,\lfloor n/a_2\rfloor\le 10^5\) |
| 4 | 5 | \(n\le 10^{13}\); \(\lfloor n/a_1\rfloor\le 10^5\) |
| 5 | 20 | \(n\le 10^{13}\); \(a_1,a_2,a_3\le 10^3\) |
| 6 | 40 | Không có giới hạn thêm |
Trong từng phần:
- Giải đúng mọi dữ liệu mà \(a_1,a_2,a_3\) đôi một nguyên tố cùng nhau nhận được \(60\%\) số điểm của phần đó.
- Giải đúng mọi dữ liệu nhận được \(100\%\) số điểm của phần đó.
Ví dụ
Ví dụ 1
Input
10
5 3
7 0
7 1Output
8Ví dụ 2
Input
1000000
114514 114
114514 810
200000 5Output
136032633Nguồn
Kỳ thi tập huấn đội tuyển quốc gia Trung Quốc 2026, CCF, giấy phép CC BY-NC.
Kỳ thi:
- CTT 2026 - Ngày 1 (2 Tháng 12., 2025)
Bình luận