Tóm tắt đề bài

Cho dãy số \(1, 2, 4, 7, 11, \ldots\). Hãy tính tổng \(S\) của \(N\) số hạng đầu tiên của dãy, với \(N\) là số nguyên dương (\(N < 10^6\)).

Phân tích

Quan sát quy luật giữa các số hạng:

• Các hiệu liên tiếp là:
  • \(2-1=1\)
  • \(4-2=2\)
  • \(7-4=3\)
  • \(11-7=4\)
• Vậy mỗi bước ta cộng thêm một số tự nhiên tăng dần: \(1,2,3,4,\ldots\)

Do đó nếu gọi \(a_1 = 1\) và \(a_k\) là số hạng thứ \(k\) thì:

• \(a_{k+1} = a_k + k\) (vì hiệu tại bước từ \(k\) sang \(k+1\) là \(k\))

Bài yêu cầu tính:

Với \(N\) tới gần \(10^6\), ta có thể tính trực tiếp theo vòng lặp \(O(N)\) là đủ nhanh trong Python.

Hướng giải quyết

Ý tưởng (theo đúng code AC)

Duy trì 3 biến:

• i: số hạng hiện tại (ban đầu \(i=1\))
• cong: độ tăng sẽ cộng vào để ra số hạng tiếp theo (ban đầu cong=1)
• S: tổng các số hạng đã cộng

Mỗi vòng lặp (tổng cộng \(N\) lần):

1. Cộng số hạng hiện tại vào tổng: S += i
2. Cập nhật số hạng tiếp theo: i += cong
3. Tăng độ tăng lên 1 cho lần sau: cong += 1

Diễn giải ví dụ \(N=5\)

• Bắt đầu: i=1, cong=1
• Lần 1: cộng \(1\), cập nhật \(i=2\), cong=2
• Lần 2: cộng \(2\), cập nhật \(i=4\), cong=3
• Lần 3: cộng \(4\), cập nhật \(i=7\), cong=4
• Lần 4: cộng \(7\), cập nhật \(i=11\), cong=5
• Lần 5: cộng \(11\)
  Tổng \(S=25\).

Lưu ý / lỗi hay gặp

• Không được cập nhật i trước khi cộng vào S (nếu không sẽ lệch mất số hạng đầu).
• Với \(N\) lớn, nên dùng kiểu số nguyên mặc định của Python (an toàn vì Python hỗ trợ số lớn).

Độ phức tạp

• Thời gian: \(O(N)\)
• Bộ nhớ: \(O(1)\)

Code tham khảo

N = int(input())
S = 0
i = 1        # số hạng hiện tại
cong = 1     # lượng tăng để ra số hạng kế tiếp

for _ in range(N):
    S += i
    i += cong
    cong += 1

print(S)