โปรแกรมหาผลรวมเลขธรรมชาติที่หาร K เหลือ R ใน C++

ภาพรวมปัญหา

โปรแกรมนี้หาผลรวมของจำนวนธรรมชาติ (Natural Numbers) ที่ ≤ N และให้เศษ R เมื่อหารด้วย K

เงื่อนไข: i % K == R โดยที่ 1 ≤ i ≤ N

วิธีแก้ปัญหา

วิธีที่ 1: Brute Force (ตรวจสอบทุกตัว)

int sumBruteForce(int N, int K, int R) {
    int sum = 0;
    for (int i = 1; i <= N; i++) {
        if (i % K == R) sum += i;
    }
    return sum;
}

Time: O(N)

วิธีที่ 2: Optimized Loop (ข้ามไปเลย K ตัว)

เลขที่หาร K เหลือ R จะอยู่ในลำดับเลขคณิต:

R, R+K, R+2K, R+3K, ... ≤ N

int sumOptimized(int N, int K, int R) {
    int sum = 0;
    // เริ่มจาก R (หรือ R+K ถ้า R=0 เพราะ Natural Number เริ่มที่ 1)
    for (int i = (R == 0 ? K : R); i <= N; i += K) {
        sum += i;
    }
    return sum;
}

Time: O(N/K) - เร็วกว่ามากเมื่อ K ใหญ่

วิธีที่ 3: สูตรคณิตศาสตร์ (O(1))

ลำดับเลขคณิต: a, a+d, a+2d, ..., a+(m-1)d

• พจน์แรก a = R (ถ้า R > 0) หรือ K (ถ้า R = 0)
• ความต่างร่วม d = K
• พจน์สุดท้าย ≤ N

จำนวนพจน์: m = floor((N - a) / K) + 1

ผลรวม: S = m * (2a + (m-1)d) / 2 = m * (first + last) / 2

long long sumFormula(int N, int K, int R) {
    if (R == 0) R = K;  // Natural numbers เริ่มที่ 1
    if (R > N) return 0;
    
    long long first = R;
    long long last = R + ((N - R) / K) * K;
    long long m = ((last - first) / K) + 1;
    
    return m * (first + last) / 2;
}

ตัวอย่างโค้ด C++ สมบูรณ์

#include <iostream>
using namespace std;

long long sumBruteForce(int N, int K, int R) {
    long long sum = 0;
    for (int i = 1; i <= N; i++) {
        if (i % K == R) sum += i;
    }
    return sum;
}

long long sumOptimized(int N, int K, int R) {
    long long sum = 0;
    int start = (R == 0) ? K : R;  // Natural numbers เริ่มที่ 1
    for (int i = start; i <= N; i += K) {
        sum += i;
    }
    return sum;
}

long long sumFormula(int N, int K, int R) {
    if (R == 0) R = K;
    if (R > N) return 0;
    
    long long first = R;
    long long last = R + ((N - R) / K) * K;
    long long m = ((last - first) / K) + 1;
    
    return m * (first + last) / 2;
}

void testCase(int N, int K, int R) {
    cout << "N=" << N << ", K=" << K << ", R=" << R << endl;
    cout << "  Brute Force: " << sumBruteForce(N, K, R) << endl;
    cout << "  Optimized:   " << sumOptimized(N, K, R) << endl;
    cout << "  Formula:     " << sumFormula(N, K, R) << endl;
    
    // แสดงตัวเลขที่ตรงเงื่อนไข
    cout << "  Numbers: ";
    int start = (R == 0) ? K : R;
    for (int i = start; i <= N; i += K) {
        cout << i << " ";
    }
    cout << endl << endl;
}

int main() {
    cout << "=== Sum of Natural Numbers with Modulo Condition ===\n\n";
    
    // ตัวอย่างจากโจทย์
    testCase(14, 4, 1);   // 1, 5, 9, 13 = 28
    
    // ทดสอบเพิ่มเติม
    testCase(20, 3, 2);   // 2, 5, 8, 11, 14, 17, 20 = 77
    testCase(10, 5, 0);   // 5, 10 = 15 (R=0 → เริ่มที่ K=5)
    testCase(100, 7, 3);  // 3, 10, 17, ..., 94
    testCase(5, 10, 3);   // 3 (เพียงตัวเดียว)
    testCase(5, 10, 7);   // 0 (ไม่มีเลข ≤ 5 ที่หาร 10 เหลือ 7)
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

=== Sum of Natural Numbers with Modulo Condition ===

N=14, K=4, R=1
  Brute Force: 28
  Optimized:   28
  Formula:     28
  Numbers: 1 5 9 13 

N=20, K=3, R=2
  Brute Force: 77
  Optimized:   77
  Formula:     77
  Numbers: 2 5 8 11 14 17 20 

N=10, K=5, R=0
  Brute Force: 15
  Optimized:   15
  Formula:     15
  Numbers: 5 10 

N=100, K=7, R=3
  Brute Force: 731
  Optimized:   731
  Formula:     731
  Numbers: 3 10 17 24 31 38 45 52 59 66 73 80 87 94 

N=5, K=10, R=3
  Brute Force: 3
  Optimized:   3
  Formula:     3
  Numbers: 3 

N=5, K=10, R=7
  Brute Force: 0
  Optimized:   0
  Formula:     0
  Numbers: 

การวิเคราะห์ตัวอย่าง N=14, K=4, R=1

ความซับซ้อนเปรียบเทียบ

ข้อควรระวัง

• R = 0 กรณีพิเศษ: Natural numbers เริ่มที่ 1 ดังนั้นตัวแรกคือ K ไม่ใช่ 0
• Overflow: ใช้ long long สำหรับ N ใหญ่ (N ~ 10⁹)
• R ≥ K: ไม่เป็นไปได้ (Modulo ให้ค่า 0 ถึง K-1) ควร Validate Input
• K = 0: Division by Zero - ต้องตรวจสอบ