51nod 1138 連續整數的和(牛逼)

1138 連續整數的和

基準時間限制：1 秒 空間限制：131072 KB 分值: 10  難度：2級算法題

 收藏

 關注 給出一個正整數N，将N寫為若幹個連續數字和的形式(長度 >= 2)。例如N = 15，可以寫為1 + 2 + 3 + 4 + 5，也可以寫為4 + 5 + 6，或7 + 8。如果不能寫為若幹個連續整數的和，則輸出No Solution。 Input

輸入1個數N(3 <= N <= 10^9)。      

Output

輸出連續整數中的第1個數，如果有多個按照遞增序排列，如果不能分解為若幹個連續整數的和，則輸出No Solution。      

Input示例

15      

Output示例

1
4
7      

        思路：

   根據所學的等差數列和公式  Sn=a1*n+n(n-1)*d/2;

 這裡所連續,是以可以公式轉變為 : 

（1）公式演變第一步:Sn=a*n+n*(n-1)/2;

（2）公式演變第二步:a=(Sn-n*(n-1)/2)/n;

 據題意，我們隻要求a(a為整數)，那麼下一步思路為周遊n,判斷一下(Sn-n*(n-1)/2)%n，那麼問題來了，n周遊到多少足夠停止？？

 那麼回到公式(1) 轉變一下 :2*Sn==(2a+n-1)*n ,因為a>=1,是以 2a-1>1,是以 (2a+n-1)*n>n^2;

 2*Sn==n^2---->也就是說n隻要周遊到sqrt(2*Sn)就可以,因為超過了n那麼就已經n^2超過2*Sn 

 直接上代碼:

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <cmath>
typedef long long ll;
int main(){
    ll n;
    while(scanf("%lld",&n)!=EOF){
       int k=sqrt(2*n);
       int flag=1;
       for(int i=k;i>=2;i--){
            if((n-i*(i-1)/2)%i==0){
                ll a=(n-i*(i-1)/2)/i;
                flag=0;
                printf("%lld\n",a);
            }
       }
       if(flag){
        printf("No Solution\n");
       }
    }
    return 0;
}