หา 3 จำนวน ≤ N ที่ LCM มากที่สุดใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะหา 3 จำนวนเต็มที่ ≤ N ซึ่งมี LCM (Least Common Multiple) มากที่สุด

LCM คืออะไร?

LCM (Least Common Multiple) = ตัวคูณร่วมน้อยที่สุดของชุดจำนวน
ถ้าจำนวนไม่มีตัวหารร่วม (coprime) LCM = ผลคูณของทุกจำนวน

ขั้นตอนการแก้ปัญหา

1. ถ้า N เป็น เลขคี่: 3 จำนวนคือ N, N-1, N-2
2. ถ้า N เป็น เลขคู่ และ GCD(N, N-3) = 1: 3 จำนวนคือ N, N-1, N-3
3. อื่นๆ: 3 จำนวนคือ N-1, N-2, N-3

เหตุผล

• เลขคี่: N, N-1, N-2 เป็นคู่ละคู่นึงร่วมเฉพาะ (coprime pairwise) → LCM = ผลคูณ
• เลขคู่: N และ N-2 เป็นเลขคู่ร่วมกัน (มีตัวหาร 2) → LCM ไม่ใช่ผลคูณ
  ต้องหลีกเลี่ยง N และ N-2 → เลือก N, N-1, N-3 (ถ้าร่วมเฉพาะ) หรือ N-1, N-2, N-3

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

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

void threeNumbersWithMaxLCM(int n) {
    if (n % 2 != 0) {
        // เลขคี่
        cout << n << " " << (n - 1) << " " << (n - 2);
    } else if (__gcd(n, (n - 3)) == 1) {
        // เลขคู่ และ N กับ N-3 ร่วมเฉพาะ
        cout << n << " " << (n - 1) << " " << (n - 3);
    } else {
        // เลขคู่ และ N กับ N-3 ไม่ร่วมเฉพาะ
        cout << (n - 1) << " " << (n - 2) << " " << (n - 3);
    }
    cout << endl;
}

int main() {
    int n = 18;
    threeNumbersWithMaxLCM(n);
    return 0;
}

ผลลัพธ์

17 16 15

N=18 (คู่), GCD(18,15)=3 ≠ 1 → เลือก 17, 16, 15
LCM(17,16,15) = 17×16×15 = 4080 (ร่วมเฉพาะคู่ละคู่)

กรณีพิเศษ N ≤ 2

โค้ดควรเพิ่มการตรวจสอบ N < 3 เพราะไม่มี 3 จำนวนที่ต่างกัน ≤ N

สรุป

กฎง่ายๆ สำหรับหา 3 จำนวน LCM สูงสุด ≤ N: เลขคี่เลือก 3 ตัวติดกัน, เลขคู่หลีกเลี่ยงคู่ที่มีตัวหาร 2 ร่วมกัน หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ