题解 P1147 【连续自然数和】

gzw2005 · 2018-01-21 10:56:06 · 题解

本蒟蒻第一篇题解

设首项为 L，末项为 R，那么 {\rm sum}(L,R)=\dfrac{(L+R)(R-L+1)}{2}=M.

即 (L+R)(R-L+1)=2M.

可以把 2M 分解成两个数之积，枚举假设分成了两个数 k_1,k_2，我们令 k_1<k_2，

可以列一个二元一次方程组\begin{cases} R-L+1=k_1\\ L+R=k_2 \end{cases}，

解得 \begin{cases} L=\dfrac{k_2-k_1+1}{2}\\ R=\dfrac{k_1+k_2-1}{2} \end{cases}.

显然当 k_1,k_2 一奇一偶 时，L,R 才是整数.

但是 L=R 的情况是被不允许的，

即 \dfrac{k_2-k_1+1}{2}\neq\dfrac{k_1+k_2-1}{2}，即 k_1\neq1.

#include<bits/stdc++.h>
using namespace std;
int m;
int main(){
    cin>>m;
    for(int k1=sqrt(2*m);k1>1;k1--)//枚举k1(注意是k1>1而不是k1>=1)
        if(2*m%k1==0 && (k1+2*m/k1)%2){//如果K2是整数而且与K1一奇一偶
            int k2=2*m/k1;
            cout<<(k2-k1+1)/2<<" "<<(k1+k2-1)/2<<endl;//输出答案
        }
    return 0;
}

时间复杂度 O(\sqrt M).

（upd：\rm LATEX 优化）