Bài 2: (4.0 điểm) CHÍNH PHƯƠNG

Số chính phương là số có thể viết dưới dạng bình phương của một số tự nhiên. Ví dụ: 1, 4, 49 là các số chính phương còn 2, 5, 20 không phải là số chính phương.

Hôm nay, thầy giáo cho Minh bài toán sau:

Cho số tự nhiên n, sau đó phân tích n = k1 + k2 + k3 + k4 + ... Trong đó, các giá trị k1, k2, k3, k4,... được tìm theo quy tắc:

• Tìm số chính phương k1 lớn nhất không vượt quá n.

• Tiếp theo, thực hiện tương tự bước trên với n = n - k1 để tìm k2.

• Để tìm k3, k4,... thực hiện tương tự như trên cho đến khi n = 0.

Hãy tính giá trị của S = (k1)^1+ (k2)^2 + (k3)^3 + (k4)^4 + ...

Theo em, giá trị của S là bao nhiêu?

Dữ liệu: Đọc từ thiết bị chuẩn gồm một số nguyên dương n (1 ≤ n ≤ 10^14)

Kết quả: Ghi ra thiết bị chuẩn giá trị S tìm được.

Ràng buộc:

Có 60% test có 1 ≤ n ≤ 10^6;

Có 40% test có 10^6< n ≤ 10^14.

Ví dụ:

Input 01:

30

Output 01:

42

Với n = 30

Ta có: n = 25 + 4 + 1 nên S = 25^1 + 4^2 + 1^3 = 42

Input 02:

25

Output 02:

25

Với n = 25, nên S = 25^1 = 25