Contest giao lưu Tin học trẻ 2024 - Lần thứ Hai (Bảng B2)

Cho \(n\), tính tổng số lượng các ước số chính phương của tất cả các số nguyên từ \(1\) đến \(n\). Cụ thể, xét các số \(1, 2, 3, \ldots, n\), hãy đếm tổng số lượng các ước số là số chính phương của tất cả các số này.

Input

• Một dòng duy nhất gồm một số nguyên dương \(n \le 10^{12}\).

Output

• Một dòng duy nhất gồm kết quả bài toán.

Example

5

6

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(1 \le n \le 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(1 \le n \le 10^6\).
• Subtask \(3\) (\(30\%\) số điểm): Không có giới hạn gì thêm.

Một dãy chia hết là một dãy các số đôi một phân biệt \(a_1, a_2, \dots, a_k\) sao cho với mọi \(i\):

• \(L \le a_i \le R\).
• \(a_{i+1}\) chia hết cho \(a_i\) nếu \(i < k\).

Bạn được cho hai số nguyên dương \(L, R\), yêu cầu:

• Xác định độ dài của dãy chia hết dài nhất (tìm \(k\) lớn nhất có thể).
• Trả lời xem có bao nhiêu dãy có độ dài như vậy.

Input

• Hai số nguyên dương \(L, R\) trên hai dòng (\(1 \le L \le R \le 10^{18}\)).

Output

• Hai số nguyên dương cách nhau một dấu cách: số lớn nhất có thể và số dãy có độ dài \(k\). Vì kết quả có thể rất lớn nên chỉ cần in ra \(9\) chữ số cuối của kết quả.

Example

3
16

3 2

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(R < 3 \times L\).
• Subtask \(2\) (\(30\%\) số điểm): \(R < 5 \times L\).
• Subtask \(3\) (\(20\%\) số điểm): \(R \le 1000\).
• Subtask \(4\) (\(20\%\) số điểm): Không có giới hạn gì thêm.

Nhân đang tập đếm các số \(1, 2, 3, 4, 5, \dots\) Nhận thấy việc này quá dễ, cộng với việc vừa mới học được phép nhân, Nhân quyết định đếm các số chính phương (là những số bằng một số nguyên nhân với chính nó) và viết chúng ra giấy và thu được một dãy dài có các số đầu tiên là \(149162536\dots\) Nhân muốn biết chữ số thứ \(n\) của dãy là bao nhiêu. Các bạn hãy tính giúp Nhân nhé.

Input

• Một số nguyên dương duy nhất \(n\) (\(1 \le n \le 10^{18}\)).

Output

• Chữ số thứ \(n\) của dãy.

Example

10

4

Subtask

• Subtask 1 (\(30\%\) số điểm): \(n \le 1000\).
• Subtask 2 (\(30\%\) số điểm): \(n \le 10^{12}\).
• Subtask 3 (\(40\%\) số điểm): Không có giới hạn gì thêm.

Có \(n\) người tham gia một cuộc thi. Người thứ \(i\) có chỉ số sức mạnh là \(a_i\). Ban tổ chức muốn thực hiện ghép hai người thành một đội để thu được \(\lfloor\frac{n}{2}\rfloor\) đội thi (nếu \(n\) lẻ thì sẽ có một người bị loại) sao cho chênh lệch sức mạnh tối đa của hai đội bất kỳ là nhỏ nhất. Biết rằng, chỉ số sức mạnh của một đội gồm hai người \((u, v)\) sẽ là \(a_u + a_v\). Hãy giúp ban tổ chức tìm ra cách ghép tối ưu.

Input

• Dòng đầu tiên gồm một số nguyên dương \(n \le 3 \times 10^5\) – số người trong cuộc thi.
• Dòng tiếp theo gồm \(n\) số nguyên \(0 \le a_i \le 10^9\).

Output

• Một dòng duy nhất gồm chênh lệch sức mạnh nhỏ nhất có thể thu được.

Example

6
1 1 1 2 2 3

1

Scoring

• Subtask 1 (\(30\%\) số điểm): \(n\) chẵn.
• Subtask 2 (\(30\%\) số điểm): \(n \le 1000\) và \(n\) lẻ.
• Subtask 3 (\(20\%\) số điểm): \(a_i \le 1\).
• Subtask 4 (\(20\%\) số điểm): \(n\) lẻ.