数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
广告