ตรวจสอบว่าจำนวนธรรมชาติ 1 ถึง N แบ่งเป็น 2 ชุดได้หรือไม่ (ผลรวมต่าง m และร่วมเฉพาะ) ใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะตรวจสอบว่าจำนวนธรรมชาติจาก 1 ถึง n สามารถแบ่งออกเป็น 2 ชุดได้หรือไม่ โดยต้องเงื่อนไข 2 ข้อ:

1. ผลต่างสัมบูรณ์ของผลรวมทั้งสองชุดเท่ากับ m
2. GCD (ตัวหารร่วมมาก) ของผลรวมทั้งสองเป็น 1 (คือ ร่วมเฉพาะ / co-prime)

หลักการคำนวณ

ผลรวมของจำนวนธรรมชาติ 1 ถึง n คือ: total = n(n+1)/2

ให้ผลรวมชุดที่ 1 = sumOne, ชุดที่ 2 = sumTwo

sumOne + sumTwo = total
sumOne - sumTwo = m

แก้สมการได้: sumOne = (total + m) / 2, sumTwo = total - sumOne

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

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

bool canSplitIntoTwoHalves(int n, int m) {
    int total_sum = (n * (n + 1)) / 2;
    int sumOne = (total_sum + m) / 2;
    int sumTwo = total_sum - sumOne;
    
    // ตรวจสอบเงื่อนไขพื้นฐาน
    if (total_sum < m) return false;
    
    // ตรวจสอบสมการและ GCD
    if (sumOne + sumTwo == total_sum && sumOne - sumTwo == m) {
        return (__gcd(sumOne, sumTwo) == 1);
    }
    return false;
}

int main() {
    int n = 10, m = 17;
    if (canSplitIntoTwoHalves(n, m)) {
        cout << "Can split";
    } else {
        cout << "Can't split";
    }
    return 0;
}

ผลลัพธ์

Can split

คำอธิบาย: n=10, total=55, sumOne=(55+17)/2=36, sumTwo=19, diff=17, gcd(36,19)=1 ✓

สรุป

โปรแกรมตรวจสอบความเป็นไปได้ของการแบ่งชุดโดยใช้คณิตศาสตร์พื้นฐานและ GCD หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ