โปรแกรมหาผลรวมตัวคูณของสองจำนวนภายใต้ N ใน C++

ภาพรวมปัญหา

โปรแกรมนี้หาผลรวมของตัวเลขที่น้อยกว่า N และเป็นตัวคูณของ M1 หรือ M2 (หรือทั้งคู่)

เงื่อนไข: i < N และ (i % M1 == 0 หรือ i % M2 == 0)

ตัวอย่าง

N = 13, M1 = 4, M2 = 6
Multiples of 4: 4, 8, 12
Multiples of 6: 6, 12
Union: 4, 6, 8, 12
Sum = 4 + 6 + 8 + 12 = 30

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

วิธีที่ 1: Brute Force O(N)

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

วิธีที่ 2: สูตรคณิตศาสตร์ O(1) - Inclusion-Exclusion Principle

ใช้หลักการรวม-ตัดออก (Inclusion-Exclusion):

Sum = Sum(M1) + Sum(M2) - Sum(LCM(M1, M2))

โดยที่ Sum(X) = ผลรวมตัวคูณของ X ที่ < N

ตัวคูณของ X: X, 2X, 3X, ..., kX โดยที่ k = floor((N-1)/X)

ผลรวม = X * (1 + 2 + ... + k) = X * k * (k + 1) / 2

ฟังก์ชันช่วย: LCM และ GCD

long long gcd(long long a, long long b) {
    while (b) {
        long long t = b;
        b = a % b;
        a = t;
    }
    return a;
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;  // ป้องกัน Overflow ด้วยการหารก่อนคูณ
}

ฟังก์ชันคำนวณผลรวมตัวคูณ

long long sumMultiples(long long N, long long X) {
    if (X == 0) return 0;
    long long k = (N - 1) / X;  // จำนวนตัวคูณที่ < N
    return X * k * (k + 1) / 2;
}

long long sumFormula(int N, int M1, int M2) {
    long long lcmVal = lcm(M1, M2);
    return sumMultiples(N, M1) + sumMultiples(N, M2) - sumMultiples(N, lcmVal);
}

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

#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    while (b) {
        long long t = b;
        b = a % b;
        a = t;
    }
    return a;
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

long long sumMultiples(long long N, long long X) {
    if (X == 0) return 0;
    long long k = (N - 1) / X;
    return X * k * (k + 1) / 2;
}

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

long long sumFormula(int N, int M1, int M2) {
    long long lcmVal = lcm(M1, M2);
    return sumMultiples(N, M1) + sumMultiples(N, M2) - sumMultiples(N, lcmVal);
}

void testCase(int N, int M1, int M2) {
    cout << "N=" << N << ", M1=" << M1 << ", M2=" << M2 << endl;
    cout << "  Brute Force: " << sumBruteForce(N, M1, M2) << endl;
    cout << "  Formula:     " << sumFormula(N, M1, M2) << endl;
    
    // แสดงตัวเลข
    cout << "  Numbers: ";
    for (int i = 1; i < N; i++) {
        if (i % M1 == 0 || i % M2 == 0) cout << i << " ";
    }
    cout << endl << endl;
}

int main() {
    cout << "=== Sum of Multiples Below N ===\n\n";
    
    testCase(13, 4, 6);    // 4,6,8,12 = 30
    testCase(24, 4, 7);    // 4,7,8,12,14,16,20,21 = 102
    testCase(100, 3, 5);   // Classic Project Euler Problem 1
    testCase(1000, 3, 5);  // Large test
    testCase(10, 2, 4);    // M2 เป็นตัวคูณของ M1
    testCase(20, 6, 8);    // LCM = 24 > 20
    
    return 0;
}

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

=== Sum of Multiples Below N ===

N=13, M1=4, M2=6
  Brute Force: 30
  Formula:     30
  Numbers: 4 6 8 12 

N=24, M1=4, M2=7
  Brute Force: 102
  Formula:     102
  Numbers: 4 7 8 12 14 16 20 21 

N=100, M1=3, M2=5
  Brute Force: 2318
  Formula:     2318
  Numbers: 3 5 6 9 10 12 15 18 20 21 24 25 27 30 33 35 36 39 40 42 45 48 50 51 54 55 57 60 63 65 66 69 70 72 75 78 80 81 84 85 87 90 93 95 96 99 

N=1000, M1=3, M2=5
  Brute Force: 233168
  Formula:     233168
  Numbers: (many)...

N=10, M1=2, M2=4
  Brute Force: 20
  Formula:     20
  Numbers: 2 4 6 8 

N=20, M1=6, M2=8
  Brute Force: 42
  Formula:     42
  Numbers: 6 8 12 16 18 

การวิเคราะห์ตัวอย่าง N=24, M1=4, M2=7

กรณีพิเศษ: M2 เป็นตัวคูณของ M1

N=10, M1=2, M2=4
Multiples of 2: 2, 4, 6, 8 (Sum=20)
Multiples of 4: 4, 8 (Sum=12)
LCM(2,4)=4: 4, 8 (Sum=12)
Total = 20 + 12 - 12 = 20  ✓ (ไม่ได้นับซ้ำ 4, 8)

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

ขยายเป็นหลายจำนวน (Multiple Numbers)

สำหรับหาผลรวมตัวคูณของ k จำนวน ใช้ Inclusion-Exclusion ทั่วไป:

Sum = Σ Sum(Mi) - Σ Sum(LCM(Mi,Mj)) + Σ Sum(LCM(Mi,Mj,Mk)) - ...

ซับซ้อน O(2^k) เหมาะ k ≤ 20

ประยุกต์ใช้

• Project Euler Problem 1
• การคำนวณทางคณิตศาสตร์จำนวน (Number Theory)
• การวิเคราะห์อัลกอริทึมที่เกี่ยวข้องกับความถี่
• การแก้ปัญหา Combinatorics