Trong hướng dẫn này, chúng ta phải tìm xem các số tự nhiên từ 1 đến n có được chia thành hai nửa hay không. Nó phải đáp ứng các điều kiện sau.
-
Chênh lệch tuyệt đối giữa tổng hai chuỗi phải là m.
-
Và GCD của hai tổng phải là 1, tức là đồng nguyên tố.
Tổng của n số tự nhiên đầu tiên là (n * (n + 1)) / 2. Chúng ta có thể tìm sumOne và sumTwo khi chúng ta có tổng tổng và hiệu số m. Xem các phương trình dưới đây.
sumOne + sumTwo = (n*(n+1))/2 sumOne - sumTwo = m
Ví dụ
Kiểm tra xem tổng tuyệt đối có bằng m hay không. Và sau đó kiểm tra GCD.
#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;
}
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;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
Can split
Kết luận
Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.