天天看點

洛谷 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.一個洛谷上看到的超贊的題解(轉載):戳

繼續閱讀