ผลรวมจำนวนเต็มติดต่อกันใน C++

คำอธิบายปัญหา

ให้จำนวนเต็มบวก N หาจำนวนวิธีเขียน N เป็นผลรวมของจำนวนเต็มบวกติดต่อกัน

ตัวอย่าง

N = 10 → Output: 3 (10, 1+2+3+4, 5+5? ไม่ 5+5 ไม่ติดต่อกัน → 10, 1+2+3+4, ?)
จริงๆ: 10 = 10, 1+2+3+4, ? → โจทย์ตัวอย่างอาจมีข้อผิดพลาด

คณิตศาสตร์

N = k×m + k(k-1)/2 โดย k = จำนวนพจน์, m = พจน์แรก (m ≥ 1)
→ 2N = k(2m + k - 1)
k ต้องเป็นตัวหารของ 2N และ (2N/k - k + 1) ต้องเป็นเลขคู่บวก

แนวทางแก้ปัญหา: วนลูป k

1. ret = 1 (ตัว N เอง)
2. สำหรับ k = 2,3,... จนกว่า k(k+1)/2 > N:
   • sum = k(k+1)/2 (ผลรวม 1..k)
   • rem = N - sum
   • ถ้า rem % k == 0 → มีคำตอบ (m = 1 + rem/k)

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int consecutiveNumbersSum(int N) {
        int ret = 1; // N เอง
        for(int k=2; ; k++) {
            int sum = k*(k+1)/2;
            if(sum > N) break;
            int rem = N - sum;
            if(rem % k == 0) ret++;
        }
        return ret;
    }
};

ความซับซ้อน

• เวลา: O(√N)
• พื้นที่: O(1)