題目描述
對一個給定的自然數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.一個洛谷上看到的超贊的題解(轉載):戳