Hồng và Hà đang ôn tập nội dung kiến thức về phân số. Để kiểm tra kiến thức của Hồng, Hà yêu cầu Hồng tính tổng 2 phân số: 3/4+5/6. Hồng thấy nó khá đơn giản nên liền đưa ra kết quả là 19/12. sau khi đưa ra kết quả cho Hà, Hồng cũng muốn kiểm tra kiến thức của Hà, nên Hồng yêu cầu:

Cho một dãy các phân số, hãy tính tổng các phân số đó, biết các phân số này đều có tử số và mẫu số là các số nguyên dương. Sau một lúc suy nghĩ Hà vẫn chưa đưa ra được kết quả.

Em hãy lập trình giúp Hà giải bài toán trên.

Dữ liệu vào đọc từ tập PHANSO.INP:

• Dòng đầu tiên chứa số nguyên dương n là số lượng phân số;
• Tiếp theo gồm n dòng, dòng thứ i trong n dòng này chứa 2 số nguyên dương xi và yi lần lượt là tử số và mẫu số của phân số thứ i. Các số xi và yi được phân bổ sao cho trong quá trình tính toán hợp lí, thì được các kết quả nằm trong phạm vi dữ liệu kiểu số nguyên.

Dữ liệu ra ghi vào tệp PHANSO.OUT:

• Nếu kết quả là một số nguyên, thì chỉ xuất ra số nguyên tương ứng.
• Nếu tử số nhỏ hơn mẫu số thì ghi tử số và mẫu số trên cùng 1 dòng và cách nhau một dấu cách;
• Nếu tử số lớn hơn mẫu số thì ghi phân số đó dưới dạng hỗn số lần lượt theo thứ tự là phần nguyên, tử số, mẫu số, các số được ghi trên cùng một dòng và cách nhau một dấu cách.

Ví dụ: PHANSO.INP

2
4 3
3 2

PHANSO.OUT

2 5 6

Giải thích

4/3+3/2=17/6 = 2 5/6

Ràng buộc:

• 80% test tương ứng với 80% số điểm, ứng với 1<n≤3,X,Vi≤10; </li>
• 20% test tương ứng với 20% số điểm, ứng với 3<n≤100, xi,Yi ≤ 50</li>

Cho n đoạn dây cáp, đoạn dây thứ i có độ dài ai. Cần phải cắt các đoạn dây thành các đoạn sao cho có được k đoạn dây bằng nhau có độ dài nguyên. Có thể không cần cắt hết các đoạn dây đã cho. Mỗi đoạn dây bị cắt có thể có phần còn thừa khác 0.

Yêu cầu: Xác định độ dài lớn nhất của đoạn dây có thể nhận được. Nếu không có cách cắt thì đưa ra số 0.

Dữ liệu vào đọc từ tập DAYCAP.INP:

• Dòng đầu tiên chứa hai số nguyên dương n, k. (1 < n ≤ 10^5,1 ≤ k ≤ 10^18).
• Tiếp theo là n dòng, dòng thứ i trong n dòng này chứa số nguyên dương a; (1 < a; ≤ 10), là độ dài của dây cáp thứ 2.

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

Ví dụ:

DAYCAP.INP

3 5
48
29
6

DAYCAP.OUT

14

Giải thích: Cắt 3 đoạn dây có độ dài lần lượt là 48, 29, 6 để có 5 đoạn dài nhất với độ dài bằng nhau, cách cắt tối ưu là:

• Dây thứ 1: Cắt được 3 đoạn độ dài 14
• Dây thứ 2: Cắt được 2 đoạn độ dài 14

Phần dư còn lại của 3 dây tương ứng là 6, 1, 6.

An là một học sinh rất thông minh và ham học hỏi. Biết được điều này, thầy giao cho An một bài tập số học về nhà, đó là: Tìm công thức tính tổng ước dương của N!. Sau một ngày nghiên cứu, An đã tìm ra công thức. Để kiểm chứng công thức của mình, An đã nhờ một bạn trong đội tuyển Tin học, tính tổng ước dương của giai thừa một vài số.

Yêu cầu: Hãy giúp An, tính tổng ước dương của giai thừa các số An đã nhờ.

Dữ liệu ra ghi vào tệp BTVN.INP:

• Dòng đầu tiên chứa một số nguyên dương T (1≤T≤ 10);
• T dòng tiếp theo, dòng thứ i chứa số nguyên dương N thứ i, là số mà An nhờ kiểm tra (1≤ N ≤200).

Dữ liệu ra ghi vào tệp BTVN.OUT:

Gồm T dòng, dòng thứ i trong T dòng gồm một số là tổng ước dương của N! ứng với số N thứ i mà An đưa ra.

Ví dụ: BTVN.INP

2
3
4

BTVN.OUT

12
60

Giải thích

• 3!=1x2x3 = 6 có 4 ước: 1, 2, 3, 6; Tổng các ước là 12
• 4! = 1 x 2x3x4 = 24 có 8 ước: 1, 2, 3, 4, 6, 8, 12, 24; Tổng các ước là 60

Ràng buộc:

• 50% test tương ứng với 50% số điểm, ứng với N ≤ 15.
• 25% test tương ứng với 25% số điểm, ứng với N < 20.
• 25% test còn lại tương ứng với 25% số điểm không có giới hạn gì thêm.

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