Kiểm tra N số tự nhiên đầu tiên chia thành 2 tập có hiệu M và tổng nguyên tố cùng nhau C++

Giới thiệu

Cho số tự nhiên N và M. Kiểm tra xem có thể chia tập {1, 2, ..., N} thành 2 tập con thỏa mãn:

• Hiệu tuyệt đối giữa tổng 2 tập = M.
• Ước chung lớn nhất (GCD) của 2 tổng = 1 (nguyên tố cùng nhau).

Toán học

Tổng N số đầu: S = N(N+1)/2.
Gọi tổng 2 tập là sum1, sum2:
sum1 + sum2 = S
sum1 - sum2 = M
→ sum1 = (S + M)/2, sum2 = (S - M)/2

Điều kiện: S ≥ M, (S+M) chẵn, GCD(sum1, sum2) = 1.

Mã nguồn ví dụ

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

bool canSplitIntoTwoHalves(int n, int m) {
    int total_sum = (n * (n + 1)) / 2;
    if (total_sum < m) return false;
    if ((total_sum + m) % 2 != 0) return false;
    int sumOne = (total_sum + m) / 2;
    int sumTwo = total_sum - sumOne;
    return (__gcd(sumOne, sumTwo) == 1);
}

int main() {
    int n = 10, m = 17;
    if (canSplitIntoTwoHalves(n, m)) cout << "Có thể chia";
    else cout << "Không thể chia";
    return 0;
}

Kết quả đầu ra

Có thể chia

Kết luận

Với N=10, M=17: tổng = 55, sum1=36, sum2=19, hiệu=17, GCD(36,19)=1 → thỏa mãn. Nếu bạn có thắc mắc, hãy để lại bình luận bên dưới.