資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中將前 N 個自然數分成兩個和的差為給定值且互質的集合
在本教程中，我們必須確定是否可以將從 1 到 n 的自然數分成兩個部分。它必須滿足以下條件。
兩個序列和的絕對差應為 m。
並且兩個和的 GCD 應為 1，即互質。
前 n 個自然數的和為 (n*(n+1))/2。由於我們擁有總和和差 m，因此我們可以找到 sumOne 和 sumTwo。請參閱以下等式。
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
結論
如果您在本教程中有任何疑問，請在評論部分中提出。
更新於: 2020-12-29
60 次瀏覽
廣告