洛谷 p1147 連續自然數和

題目描述

對一個給定的自然數M，求出所有的連續的自然數段，這些連續的自然數段中的全部數之和為M。

例子：1998+1999+2000+2001+2002 = 10000，是以從1998到2002的一個自然數段為M=10000的一個解。

輸入輸出格式

輸入格式：

包含一個整數的單獨一行給出M的值（10 <= M <= 2,000,000）。

輸出格式：

每行兩個自然數，給出一個滿足條件的連續自然數段中的第一個數和最後一個數，兩數之間用一個空格隔開，所有輸出行的第一個按從小到大的升序排列，對于給定的輸入資料，保證至少有一個解。

輸入輸出樣例

輸入樣例#1： 10000

輸出樣例#1：

18 142

297 328

388 412

1998 2002

1.利用等差數列求和公式： Sn=n(a1+an)2 ，枚舉左右邊界，求和的結果為M的時候就把它輸出

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;

ll f(ll x,ll y)
{
    return (x+y)*(y-x+)>>;//（首項+末項）*項數/2.
    //n>>1就是n/2的意思，利用位運算加快速度
}
int main()
{
    ll n;
    scanf("%lld",&n);
    for(ll x=;x<=(n>>);x++)//一個小小的優化：當x>n/2時不再有x,y符合題意
        for(ll y=x+;y<=n;y++)
        {
            if(f(x,y)==n){
                printf("%lld %lld\n",x,y);
            }
        }
}
           

雖然做了一些優化，還是逾時了兩個點，也許加上快讀？？

不是标算。

2.偉大的字首和：

一個數組f[]存儲[1,2000000]區間的字首和，然後就可以實作O(1)複雜度的等差數列求和

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;

const int N=;
int f[N];

void init()//initialize，求出字首和
{
    f[]=;
    for(int i=;i<=N;i++)
        f[i]=f[i-]+i;
}
int main()
{
    int n;
    scanf("%intd",&n);
    init();
    int tmp=(n>>);
    for(int x=;x<=tmp;x++)
        for(int y=x+;y<=n;y++)
        {
            if((f[y]-f[x-])==n)//x加到y就是f(y)-f(x-1)
                printf("%d %d\n",x,y);
            if((f[y]-f[x-])>n) break;//這一句很重要，加起來比n還大的話就退出
        }
}
           

3.一個洛谷上看到的超贊的題解（轉載）：戳