Nhập vào một số nguyên dương N. Bạn hãy tính và in ra S là tổng của tất cả các ước số dương của mọi số nguyên từ 1 đến N. Do kết quả có thể vượt giới hạn số nguyên 32-bit, hãy sử dụng kiểu dữ liệu số nguyên lớn 64-bit (long long trong C++, số nguyên mặc định trong Python).

Input: Một dòng chứa số nguyên N (1 <= N <= 10^6).

Output: Tổng các ước số của mọi số từ 1 đến N.

Ví dụ:

Input:

4

Output:

15

(Giải thích: Ước của 1 là 1. Ước của 2 là 1,2. Ước của 3 là 1,3. Ước của 4 là 1,2,4. Tổng = 1 + 1+2 + 1+3 + 1+2+4 = 15).

Cho N tấm vách ngăn thẳng đứng được đặt trên mặt phẳng ngang tại các tọa độ i = 1, 2, ..., N. Tấm vách thứ i có chiều cao là Hi. Nếu ta chọn 2 tấm vách bất kỳ ở vị trí i và j (i < j), chúng sẽ tạo thành một bể nước với thể tích là (j - i) * min(Hi, H_j). Hãy tìm ra 2 tấm vách để tạo thành bể chứa được lượng nước lớn nhất.

Input:

Dòng 1: N (2 <= N <= 10^5).

Dòng 2: N số nguyên Hi (1 <= Hi <= 10^4).

Output: Thể tích nước lớn nhất có thể chứa.

Ví dụ:

Input:

9
1 8 6 2 5 4 8 3 7

Output:

49

(Giải thích: Chọn vách số 2 (cao 8) và vách số 9 (cao 7). Thể tích = (9 - 2) * min(8, 7) = 7 * 7 = 49).

Đơn vị thi công nhận được một cao độ mặt đất biểu diễn bằng mảng A gồm N số. Máy xúc có một nút điều chỉnh công suất K. Đơn vị phải thực hiện thao tác sau đối với mọi vị trí i: Hoặc là cộng thêm K vào Ai, hoặc là trừ đi K từ Ai. Yêu cầu làm sao cho độ chênh lệch giữa vị trí cao nhất và vị trí thấp nhất sau khi điều chỉnh là nhỏ nhất có thể.

Input:

Dòng 1: N, K (1 <= N <= 10^5, 0 <= K <= 10^4).

Dòng 2: N số nguyên Ai (1 <= Ai <= 10^4).

Output: Độ chênh lệch nhỏ nhất đạt được.

Ví dụ:

Input:

3 3
1 5 6

Output:

2

(Giải thích: Điều chỉnh mảng thành [1+3, 5-3, 6-3] = [4, 2, 3]. Max là 4, Min là 2. Chênh lệch là 2).

Cơ quan thống kê cần đếm số lượng các số nguyên nằm trong đoạn từ L đến R thỏa mãn điều kiện: Tổng các chữ số của số đó đúng bằng một giá trị S cho trước. Vì L và R có thể rất lớn, bạn hãy thiết kế một thuật toán quy hoạch động tối ưu để đếm nhanh chóng.

Input: Một dòng chứa 3 số nguyên L, R, S (1 <= L <= R <= 10^18, 1 <= S <= 162).

Output: Số lượng các số thỏa mãn.

Ví dụ:

Input:

10 20 2

Output:

2

(Giải thích: Trong đoạn từ 10 đến 20, chỉ có 11 và 20 là có tổng chữ số bằng 2).