Tổng các số nguyên liên tiếp trong C++

Cho số nguyên dương N, đếm số cách viết N thành tổng các số nguyên dương liên tiếp.

Ví dụ: 10 → 3 cách (10, 1+2+3+4, 10=5+5? sửa: 10 = 10, 1+2+3+4, ?). Code cho ra 2 (10 và 1+2+3+4).

Giải thuật

1. Số cách = số ước lẻ của N (hoặc số cách viết N = k * m với k lẻ).
2. Duyệt độ dài i từ 2: sum = i*(i+1)/2. Nếu sum > N thì dừng.
3. rem = N - sum. Nếu rem % i == 0 thì có 1 cách (bắt đầu từ rem/i + 1).
4. Khởi tạo ret = 1 (cách viết N một mình).

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int consecutiveNumbersSum(int N) {
        int ret = 1;
        for(int i = 2; ; i++){
            int sum = (i * (i + 1)) / 2;
            if(sum > N) break;
            int rem = N - sum;
            ret += (rem % i == 0);
        }
        return ret;
    }
};
int main(){
    Solution ob;
    cout << (ob.consecutiveNumbersSum(10));
}

Đầu vào

10

Đầu ra

2