给出一个正整数N，将N写为若干个连续数字和的形式(长度 >= 2)。例如N = 15，可以写为1 + 2 + 3 + 4 + 5，也可以写为4 + 5 + 6，或7 + 8。如果不能写为若干个连续整数的和，则输出No Solution。

 收起

输入

输入1个数N(3 <= N <= 10^9)。

输出

输出连续整数中的第1个数，如果有多个按照递增序排列，如果不能分解为若干个连续整数的和，则输出No Solution。

输入样例

15

输出样例

1
4
7

分析：

假设[a,a+k-1]满足和=n

a，a+1, a+2,……a+k-1

k*a+k*(k-1)/2=n

k^2+(2*a-1)k-2n=0

这题一开始想的暴力枚举a，

k=【（1-2a)+(long long)(2*a-1)*(long long)(2*a-1)+8*n】/2

果断的T了

这题需要转化一下啊思想

枚举k

k^2+k=2n

取a=1，k可以取到最大不超过sqrt（2*n）

即k的取值范围（2，sqrt(2*n)）

 

超时代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		int flag=1;
	    for(int a=1;a<=n/2;a++)
		{
		  double x=(long long)(2*a-1)*(long long)(2*a-1)+8*n;
		  x=sqrt(x);
		  if(x==(int)x)
		  {
		  	if(((int)x+1-2*a)%2==0)
			{
				printf("%d\n",a);
				flag=0;
			}
		  }
		}
		if(flag==1)
			printf("No Solution\n");
	}
	return 0;
}

AC代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	
		int flag=1;
	    for(int k=sqrt(2*n);k>=2;k--)
		{
		   if((2*n+k-k*k)%(2*k)==0)
		   {
			printf("%d\n",(2*n+k-k*k)/(2*k));
			flag=0;
		   }
             
		}
		if(flag==1)
			printf("No Solution\n");

	return 0;
}