Vào đầu năm học 2024-2025, trường THPT A đã tiến hành thành lập và giảng dạy cho đội tuyển học sinh giỏi Tin học cho Kỳ thi học sinh giỏi cấp tỉnh. Để chuẩn bị tốt nhất cho học sinh, Trường đã giảng dạy 9 chuyên đề: 1. Độ phức tạp và cải tiến thuật toán; 2. Tổ hợp và số học; 3. Sắp xếp, tìm kiếm nâng cao; 4. Xử lí xâu: 5. Tham lam, Quy hoạch động; 6. Duyệt toàn bộ và nhánh cận; 7. Các thuật toán đồ thị; 8. Các thuật toán hình học; 9. Cấu trúc dữ liệu nâng cao.

Sau khi dạy xong, nhà trường đã ra một bài toán để lựa chọn 10 em làm tốt nhất tham dự Kỳ thi học sinh giỏi cấp tỉnh, bài toán như sau:

Cho ba số nguyên dương n, r, k. Gọi D (x) là tập hợp các số nguyên dương đôi một khác nhau và là ước của x. Hãy tính: n Σ Σ raak Mod M x=1 de D(x)

Trong đó, Mod là phép chia lấy dư hai số nguyên và M = 998244353.

Yêu cầu: Em hãy lập trình để giải bài toán trên.

Dữ liệu vào đọc từ tệp TC.INP: gồm một dòng duy nhất chứa ba số nguyên dương n, r, k.

Dữ liệu ra ghi vào tệp TC.OUT: một số nguyên duy nhất là kết quả bài toán.

Ví dụ: TC.INP

4 1 2

TC.OUT

37

Giải thích Với n = 4; r = 1; k 2;x lần lượt nhận các giá trị là 1,2,3,4, tương ứng với các ước là: 1; 1, 2; 1, 3; 1, 2, 4 áp dụng công thức ta có kết quả là: [11 x 12 + (11× 12 + 12 x 22) + (11 x 12 + 13 x 32) + (11 x 12 + 12 × 22 + 14 x 42)] Mod 998244353 = 37 Tương tự, biểu thức là: [21 x 12 + (21× 12 + 22 x 22) + (21 x 12 + 23 x 32) + (21 × 12 + 22 × 22 + 24 × 42)] Mod 998244353 = 368

Ràng buộc:

• Có 25% số test ứng với 25% số điểm của bài thoả mãn điều kiện: n≤ 102; r = 1; k ≤ 8; • Có 25% số test ứng với 25% số điểm của bài thoả mãn điều kiện: n≤ 106; r = 1; k ≤ 8 ; • Có 25% số test ứng với 25% số điểm của bài thoả mãn điều kiện: n≤ 2 × 106; r < M; k ≤ 3 x 103; • 25% số test còn lại ứng với 25% số điểm của bài thoả mãn điều kiện: n≤ 2 × 109; r = 1; k ≤ 4.

Nguồn