Editorial: Mathematical Algorithms TWK Open Problem #A - Dãy Số Quyết Định

1. Ý tưởng

Xét dãy số ban đầu: \(2, 8, 20, 40, 70, 112, ...\)

Theo gợi ý của đề bài, ta tính hiệu giữa các số liên tiếp (dãy hiệu thứ 1):

• \(8 - 2 = 6\)
• \(20 - 8 = 12\)
• \(40 - 20 = 20\)
• \(70 - 40 = 30\)
• \(112 - 70 = 42\)

Dãy hiệu thu được: \(6, 12, 20, 30, 42, ...\)

Tiếp tục lấy hiệu giữa các số liên tiếp trong dãy mới này (dãy hiệu thứ 2):

• \(12 - 6 = 6\)
• \(20 - 12 = 8\)
• \(30 - 20 = 10\)
• \(42 - 30 = 12\)

Dãy hiệu thứ 2 là một cấp số cộng: 6, 8, 10, 12, ...

Nhìn vào dãy hiệu thứ 1 (6, 12, 20, 30, 42, ...), ta thấy từng số đều có thể phân tích thành tích của hai số nguyên liên tiếp:

• \(D_1 = 6 = 2 * 3\)
• \(D_2 = 12 = 3 * 4\)
• \(D_3 = 20 = 4 * 5\)
  \(...\)
• \(D_k = (k + 1) * (k + 2)\)

Số thứ N của dãy ban đầu (A_N) sẽ bằng A_1 cộng với tổng các số hạng từ D_1 đến D_(N-1):
\(A_N = 2 + sum_{k=1}^{N-1} (k + 1)(k + 2)\)

Sử dụng công thức tính tổng chuỗi:
\(sum_{i=1}^{M} i(i+1) = (M * (M + 1) * (M + 2)) / 3\)

Rút gọn lại, ta thu được công thức tổng quát trực tiếp cho số thứ N:
\(A_N = (N * (N + 1) * (N + 2)) / 3\)

2.Độ phức tạp:

• Thời gian: O(1)
• Không gian: O(1)

Lưu ý: Với \(N \le 10^5\), giá trị \(N * (N + 1) * (N + 2)\) có thể lên tới 10^15, vượt quá giới hạn của kiểu số nguyên 32-bit (int), do đó cần dùng kiểu số nguyên 64-bit (long long trong C++) để tránh tràn số.