51nod 1138 连续整数的和 好题

给出一个正整数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;
}