ในบทช่วยสอนนี้ เราต้องค้นหาว่าจำนวนธรรมชาติจาก 1 ถึง n แบ่งออกเป็นสองส่วนหรือไม่ ต้องเป็นไปตามเงื่อนไขต่อไปนี้
-
ความแตกต่างที่แน่นอนระหว่างผลรวมอนุกรมทั้งสองควรเป็น m
-
และ GCD ของผลรวมทั้งสองควรเป็น 1 นั่นคือ co-primes
ผลบวกของจำนวนธรรมชาติ n ตัวแรกคือ (n*(n+1))/2เราสามารถหา sumOne และ sumTwo ได้เนื่องจากเรามีผลรวมและส่วนต่างทั้งหมด m ดูสมการด้านล่าง
sumOne + sumTwo = (n*(n+1))/2 sumOne - sumTwo = m
ตัวอย่าง
ตรวจสอบว่าผลรวมสัมบูรณ์เท่ากับ m หรือไม่ แล้วตรวจสอบ 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;
} ผลลัพธ์
หากคุณเรียกใช้โค้ดด้านบน คุณจะได้ผลลัพธ์ดังต่อไปนี้
Can split
บทสรุป
หากคุณมีข้อสงสัยใดๆ ในบทแนะนำ โปรดระบุในส่วนความคิดเห็น
