Chương trình đếm số dãy số liên tiếp dương có tổng bằng n trong C++

Cho số n. Đếm số dãy các số nguyên dương liên tiếp có tổng bằng n. Ví dụ n = 15 → 4 dãy: [1..5], [4,5,6], [7,8], [15].

Giải thuật (Cửa sổ trượt)

• begin = 1, end = 1, sum = 0.
• Mở rộng end, cộng vào sum.
• Khi sum ≥ n: thu hẹp từ begin, trừ begin khỏi sum, tăng begin. Nếu sum == n → đếm++.
• Lặp đến khi end > (n+1)/2.
• Kết quả = count + 1 (tính thêm dãy 1 phần tử [n]).

Ví dụ triển khai

#include <bits/stdc++.h>
using namespace std;

int solve(int n) {
    int begin = 1, end = 1, x = (n + 1) / 2, count = 0;
    long sum = 0;
    while (end <= x) {
        sum += end;
        while (sum >= n) {
            if (sum == n) count++;
            sum -= begin;
            begin++;
        }
        end++;
    }
    return count + 1;
}

int main() {
    cout << solve(15);
    return 0;
}

Đầu vào

15

Đầu ra

4