codefroce A.Sum of Odd Integers 思维题（并且实现输出k个奇数）

In the first test case, you can represent 33 as 33.

In the second test case, the only way to represent 44 is 1+31+3.

In the third test case, you cannot represent 1010 as the sum of three distinct positive odd integers.

In the fourth test case, you can represent 1010 as 3+73+7, for example.

In the fifth test case, you can represent 1616 as 1+3+5+71+3+5+7.

In the sixth test case, you cannot represent 1616 as the sum of five distinct positive odd integers.

题意：输入一个数n,判断其是否可以由k个不同的奇数组成。

我刚看到题时，我以为是模拟题，然后我发现比如13=1+3+9，我模拟时怎么能确定是这三个数呢？暴力？当然不行了。所以此题必定是找规律的思维题。其实模拟也是可以的后面会提到。

题解：首先我们知道奇数个奇数相加必定时奇数，偶数个偶数相加必定是偶数，所以n和k要不是同为奇数，要不就是同为偶数。

进一步我们怎么考虑？先看前n个奇数吧：

奇数：　　1　　 3　　 5　　 7　　 9 ……

前n项和：  1　　 4 　　9　　 16　　25……

可以发现: 前n个奇数的和为n²！由此我们可以想到k个不同的奇数相加时，最小值为 k² ！即n如果小于k²，就一定不能有合法的k个不同的奇数组成。

看到这，或许你还有疑问？其实我也有  。在n和k奇偶性相同时，n>k²时真的就一定能有k个不同的奇数之和为n吗？

这就是具体实现的问题了也是模拟的问题了。我们拿n=13,k=3为例。

首先我们判断上面两个条件都成立，那么我们先取前k个奇数相加为 1+3+5=9。 显然8！=13。还差4。我给这个4命一个名叫差值

怎么凑出这个4呢？最后一个奇数5，我们让他加上一个4等于9还是奇数，此时1+3+9=13。成立。

我们即可把差值都加到最后一个奇数上，这样就可以把组成求出来。

有人会想这样最后一个奇数加上差值后会不会变成偶数，以至不合法。并不会其实这个差值一定是偶数（一个数平方后奇偶性不变，故n和k² 奇偶性不变，他们的差值就一定为偶数了）！ 奇数加偶数还是奇数，这样就一定能保证该k个数是合法的了。故该结论成立。

AC代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        if(n<k*1ll*k)
        {
            printf("NO\n");
            continue;
        }
        if(n%2==0&&k%2==0)printf("YES\n");
        else if(n%2==1&&k%2==1)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

　　具体模拟实现输出k个不同的奇数:

#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
int num[10000007];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        if((n-k)%2!=0||n<k*1ll*k)
        {
        	printf("NO\n");
        	continue;
        }
        
        ll ans=0ll;int c=0;
        for(int i=1;i<=k;i++){
        	//printf("%d",2*i-1);
        	num[c++]=2*i-1;
        	ans+=2*i-1;
        }
        if(ans<n)
        num[c-1]+=(n-ans);
        for(int i=0;i<c;i++)
        printf("%d ",num[i]);
		printf("\n");
		printf("YES\n");
    }
    return 0;
}