---

B. Same Parity Summands

原创 于 2023-08-12 01:57:09 发布 · 粉丝可见 · 177 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132242243

题目：

cobol<br/>8<br/>10 3<br/>100 4<br/>8 7<br/>97 2<br/>8 8<br/>3 10<br/>5 3<br/>1000000000 9<br/>

cobol<br/>YES<br/>4 2 4<br/>YES<br/>55 5 5 35<br/>NO<br/>NO<br/>YES<br/>1 1 1 1 1 1 1 1<br/>NO<br/>YES<br/>3 1 1<br/>YES<br/>111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111120<br/>

思路：

这是一道思维题，构造算法

在这里，题目意思是 n 是 k 个元素的总和，每个元素它们的奇偶性一致，并且它们除以2余数相同

这里我们 每个元素除以 2 余数相同，就是奇偶性一致，又因为 它们当中元素肯定跟我们的 n 因子成倍数关系，所以我们可以从 分解因子 进行突破，构造出来就可以了

代码详解如下：

#include <iostream>
#define endl '\n'
#define YES puts("YES");
#define NO puts("NO");
using namespace std;
int n, k;

int other;	// 为 k - 1 个因子元素
int last;	// n - (k - 1) * other 为 k 最后一个元素


// 这里是构造得来的函数


inline bool Finds(int &i)
{
	other = (k - 1) * i;	// 我们找出符合 k - 1 个因子

	last = n - other;

	// 并判断 n - (k - 1 个因子) 后它们是否和 该因子成倍数关系
	// 并且它们的 除以 2 的余数是否相同
	// 是则输出答案即可
	if (other < n && last % i == 0 && last % 2 == i % 2)
	{
		YES;
		cout << last << ' ';
		k--;
		while (k--)
			cout << i << ' ';
		putchar('\n');
		return true;
	}
	return false;
}


inline void solve()
{
	cin >> n >> k;

	// 分解 n 的因子，因为我们总和 n 个 ai 中肯定有 n 的因子
	// 所以我们从 n 的因子中突破，对因子 构造即可获得答案
	for (int i = 1; i * i <= n; ++i)
	{
		if (n % i == 0)
		{
			if (Finds(i))
				return ;
			if (i * i != n)
			{
				int tem = n / i;
				if (Finds(tem))
					return ;
			}
		}
	}
	NO;
}

int main()
{
	int _t;
	cin >> _t;
	while (_t--)
	{
		solve();
	}

	return 0;
}

最后提交：