题目描述
You are given two positive integers $n (1≤n≤10^9)$ and $k (1≤k≤100)$. Represent the number n as the sum of k positive integers of the same parity (have the same remainder when divided by 2).
In other words, find $a1,a2,…,ak$ such that all $ai>0, n=a1+a2+…+ak$ and either all $ai$ are even or all $ai$ are odd at the same time.
If such a representation does not exist, then report it.
Input
The first line contains an integer $t (1≤t≤1000)$ — the number of test cases in the input. Next, t test cases are given, one per line.
Each test case is two positive integers $n (1≤n≤10^9)$ and $k (1≤k≤100)$.
Output
For each test case print:
YES
and the required values ai, if the answer exists (if there are several answers, print any of them);
NO if the answer does not exist.- The letters in the words
YES
andNO
can be printed in any case.
样例
8
10 3
100 4
8 7
97 2
8 8
3 10
5 3
1000000000 9
YES
4 2 4
YES
55 5 5 35
NO
NO
YES
1 1 1 1 1 1 1 1
NO
YES
3 1 1
YES
111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111120
算法1
(模拟,数学)
给定两个数 $ n $, $ k $, 求是否有$k$个数满足两个条件:
1. 这$k$个数均大于等于$1$,且同奇偶
2. 这$k$个数的和为$n$
如果有这样的$k$个数,输出”YES”,且打印任意一组,否则输出”NO”。
根据$n$和$m$的奇偶性分别讨论即可:
1. n 为奇数, k为偶数:此时不管取k个奇数还是k个偶数均无解,因为偶数个偶数和偶数个奇数的和一定都是偶数
2. n 为偶数,k为奇数:此时如果有解必为k个偶数,因为奇数个奇数的和仍然是奇数,所以必须要奇数个偶数才能凑到n
3. n为奇数,k为奇数:此时如果有解必为k个奇数,原因同上
4. n为偶数,k为偶数:次数选k个奇数和k个偶数均可
同时,本题还需要注意的是所有选择的数必须大于0,所以在每一种情况下再判断下即可
C++ 代码
#include <iostream>
using namespace std;
int main()
{
int T, n, k;
cin >> T;
while (T--)
{
cin >> n >> k;
int val = n / k;
if (n & 1) // n 是奇数
{
if (k % 2 == 0) { // k 是偶数:无解
val = -1;
}else{ // k 是奇数 : 必须k个奇数
if (val % 2 == 0){ // 平均值为偶数就必须转成奇数,加一或减一
if ((val + 1) * (k - 1) + 1 > n) val--;
else val++;
}
}
}
else // n 是偶数
{
if (k & 1) { // k 是奇数:必须k个偶数
if(val & 1){ // 平均值为奇数就必须转成偶数,加一或减一
if ((val + 1) * (k - 1) + 2 > n) val--;
else val++;
}
}
}
if (val <= 0) puts("NO");
else{
puts("YES");
for (int i = 0; i < k - 1; ++i) cout << val << ' ';
cout << n - val * (k - 1) << endl;
}
}
return 0;
}
Python 代码
T = int(input())
for _ in range(T):
n, k = map(int, input().split())
avg = n // k
if n & 1:
if k & 1 == 0:
avg = -1
else:
if avg & 1 == 0:
if (avg + 1) * (k - 1) + 1 > n:
avg -= 1
else:
avg += 1
else:
if k & 1 and avg & 1:
if (avg + 1) * (k - 1) + 2 > n:
avg -= 1
else:
avg += 1
if avg <= 0:
print("NO")
else:
a = [avg for i in range(k - 1)]
a += [n - avg * (k - 1)]
print("YES")
print(*a)