P1147 暴力解法

· · 个人记录

P1147 连续自然数和

题目链接

一开始怀着侥幸心理打了个暴力，没想到直接AC了

而且38ms,468B......太水

思路

直接把所有区间的左右端点枚举一遍

然后用等差数列公式求和就行

不开O2虽然慢了一点，但也能过

总之O2永远的神

AC代码

#include<bits/stdc++.h>
using namespace std;
template<typename T>                                //使用模板类实现的快读 
inline void read(T &x){                             //可以兼容int/long long
    x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)){
        x=x*10+(ch^48);ch=getchar();
    }return;
}
int main()
{
    int m;register int i,j;                         //加 register听说更快一点 
    read(m);
    for(int i=1;i<=m-1;i++){
        for(int j=i+1;j<=m;j++){ 
            if((i+j)*(abs(i-j)+1)/2==m) printf("%d %d\n",i,j);
            else if((i+j)*(abs(i-j)+1)/2>m) break;
            //如果得出的和已经大于m，那么继续计算和就越来越大，
            //更不可能等于m，所以直接结束这层循环 
        }
    }
    return 0;
}

等差数列公式：(首项+末项)*项数/2

水题就不加防抄袭了