Lam đang luyện thi vào lớp chuyên Tin của trường THPT chuyên XYZ. Chủ đề thầy giáo giao cho Lam tuần này là số học và yêu cầu Lam làm bài tập trên hệ thống trực tuyến. Có bài toán sau Lam loay hoay mãi chưa ra, bạn hãy giúp Lam nhé! Bài toán như sau: Cho hai số nguyên dương L và R. Hãy tính tổng tất cả các số chẵn trong đoạn [L , R].

Yêu cầu:

Viết chương trình giúp Lam giải bài toán trên.

Dữ liệu:

Vào từ tệp văn bản CAU1.INP gồm một dòng ghi hai số nguyên dương L và R (L≤R≤〖2.10〗^9 ).

Kết quả:

Ghi ra tệp văn bản CAU1.OUT một số nguyên là tổng tính được.

Ví dụ:

CAU1.INP 2 9 3 3 CAU1.OUT 20 0 Giải thích Trong đoạn [2, 9] có các số chẵn là: 2, 4, 6, 8. Tổng của chúng là 2+4+6+8 = 20 Trong đoạn [3, 3] không có số chẵn nên kết quả bằng 0

Ràng buộc:

• Có 75% số điểm tương ứng với số test có L≤R≤10^4;
• Có 25% số điểm tương ứng với số test còn lại không ràng buộc gì thêm.

Hôm nay Lam được học về chủ đề số nguyên tố. Lam biết số nguyên tố là số tự nhiên lớn hơn 1, chỉ có hai ước là 1 và chính nó. Ví dụ: 2, 3, 5, … là các số nguyên tố; các số 4, 6, 8, … không phải số nguyên tố. Lam nghĩ ra một bài toán để đố các bạn trong lớp như sau: Cho hai số nguyên dương a và b. Hãy đếm trong đoạn [a, b] có bao nhiêu số mà số lượng các ước dương của nó là một số nguyên tố.

Yêu cầu:

Các bạn hãy viết chương trình giải bài toán trên.

Dữ liệu:

Tệp văn bản CAU2.INP gồm:

• Dòng 1: chứa số nguyên dương T là số lượng các đoạn cần đếm;
• T dòng tiếp theo, mỗi dòng chứa một cặp số nguyên dương a và b.

Kết quả:

Tệp văn bản CAU2.OUT gồm T dòng, mỗi dòng là kết quả tương ứng với dữ liệu vào.

Ví dụ:

CAU2.INP

2

2 7

1 100

CAU2.OUT

5

32

Giải thích

Trong đoạn [2, 7] có 5 số thỏa mãn là 2, 3, 4, 5, 7 (vì 2, 3, 5, 7 có 2 ước dương; 4 có 3 ước dương; mà 2 và 3 đều là số nguyên tố). Số 6 không thỏa mãn vì 6 có 4 ước dương mà 4 không phải số nguyên tố. …

Ràng buộc:

• Có 40% số điểm tương ứng với số test có 1 ≤ a ≤ b ≤ 200 và T ≤10^2;
• Có 30% số điểm tương ứng với số test có 1 ≤ a ≤ b ≤ 2000 và T ≤10^3;
• Có 30% còn lại tương ứng với số test có 1 ≤ a ≤ b ≤ 106 và T ≤ 10^5.

Lam là một học sinh giỏi Toán, nhưng lại có niềm đam mê về lập trình nên Lam quyết định thi vào lớp 10 chuyên Tin mà không thi vào lớp 10 chuyên Toán. Biết được Lam sắp tới thi vào lớp 10 chuyên Tin nên Thầy giáo có bài tập về lập trình đố Lam như sau: Cho hai số nguyên dương a và b. Xét tất cả các số nguyên dương là bội của a hoặc b (nếu có hai số trùng nhau chỉ lấy một số) và sắp xếp chúng thành dãy tăng dần.

Yêu cầu:

Tìm số thứ N trong dãy sau khi đã sắp xếp.

Dữ liệu:

Tệp văn bản CAU3.INP gồm:

• Dòng 1 chứa số nguyên dương T là số test (T ≤ 10^5);
• T dòng tiếp theo, mỗi dòng chứa ba số nguyên dương a, b, N biểu thị cho một test (a, b ≤ 10^5; N ≤ 2.10^9).

Kết quả:

Tệp văn bản CAU3.OUT gồm T dòng, mỗi dòng một số nguyên là kết quả một test tương ứng.

Ví dụ:

CAU3.INP

3

4 6 9

2 3 10

3 3 2

CAU3.OUT

28

15

6

Giải thích

Các bội nguyên dương của 4 hoặc 6 theo thứ tự sau khi sắp xếp là: 4, 6, 8, 12, 16, 18, 20, 24, 28…. Vậy số thứ 9 của dãy trên là 28 …

Ràng buộc:

• Có 20% số điểm tương ứng với số test có T = 1, a = b và N ≤ 2.10^9;
• Có 30% số điểm tương ứng với số test có T = 1, a ≠ b và N ≤ 10^4;
• Có 50% số điểm tương ứng với số test không còn ràng buộc gì thêm.

Lam là một học sinh giỏi môn Tin học, các bạn trong lớp hay nhờ Lam giải các bài toán khó. Hôm nay các bạn có nhờ Lam một bài toán về xâu như sau: Cho xâu S chỉ gồm các kí tự chữ cái in thường, các kí tự trong xâu S được đánh số thứ tự từ 1 đến |S| (trong đó |S| là độ dài của xâu S) và thực hiện m lần thay đổi. Với mỗi lần thay đổi, chọn một số nguyên dương k và đảo ngược một đoạn của xâu S từ vị trí k trở về vị trí |S| - k + 1 (luôn đảm bảo k > (|S|)/2).

Yêu cầu:

Viết chương trình tìm xâu S sau m lần thay đổi.

Dữ liệu:

Vào từ tệp văn bản CAU4.INP gồm:

• Dòng thứ nhất là xâu S (2 ≤ |S| ≤ 2.10^5);
• Dòng thứ hai là số nguyên dương m (1 ≤ m ≤ 10^5);
• Dòng thứ ba là m số nguyên dương a1, a2, .., am ((|S|)/2 < ai ≤ |S|; i = 1 .. m).

Kết quả:

Ghi ra tệp văn bản CAU4.OUT gồm 1 dòng duy nhất là kết quả của bài toán.

Ví dụ:

CAU4.INP

abcdef

3

5 6 4

CAU4.OUT

fbdcea

Giải thích

Với k = 5 thì xâu "abcdef" thay đổi thành "aedcbf"

Với k = 6 thì xâu "aedcbf" lại đổi thành "fbcdea"

Với k = 4 thì xâu "fbcdea" lại đổi thành "fbdcea"

Ràng buộc:

• Có 50% số điểm tương ứng với số test có |S| ≤ 10^3 và m ≤ 10^3;
• Có 50 % số điểm tương ứng với số test không có ràng buộc gì thêm.