首页 > itarticle > 「vijos 1302」连续自然数和

「vijos 1302」连续自然数和

admin 11月 13, 2020 0

对一个给定的自然数$M$，求出所有的连续的自然数段（连续个数大于$1$），这些连续的自然数段中的全部数之和为$M$。

来源

题解

设若干个连续自然数和为$M$，其首项为$a$，末项为$b$，则共有$b-a+1$项。那么根据等差数列的求和公式，我们得出：
$$
frac{(b-a+1)(a+b)}{2}=M
$$
整理得：
$$
b^2+b-a^2+a-2M=0
$$
一个二元二次方程。所有满足上式、且满足$a<b$的正数$a,b$都是答案。但如果两个数都枚举的话时间显然不够，所以我们要将其中一个未知量设为常量，然后将方程解出来。为了枚举的方便，这里设$a$是常量，那么就能求判别式了：
$$
Delta=1-4(-a^2+a-2M)=1+4a^2-4a+8M
$$
仅当$Delta>0$成立，才可能有满足题意的$a,b$。

接着用一元二次方程的求根公式求出两根：
$$
x=frac{-1pmDelta}{2}
$$
因$b>0$，故负根舍去：
$$
b=frac{-1+Delta}{2}=frac{-1+sqrt{1+4a^2-4a+8M}}{2}
$$
于是只需要枚举$a$，然后代入上式求$b$即可。若满足$b$是整数、$Delta>0$及$a<b$，则该$a,b$是一对可行解。

注意要用long long，中途的乘方运算可能爆掉int。

以上

代码


#include <cmath>
#include <iostream>

int ()
{
    std::ios::sync_with_stdio(false);
    
    int m;
    std::cin >>m;
    for(long long a = 1; a < m; ++a)
    {
        if(1+4*a*a-4*a+8*m > 0)
        {
            double b = (-1+sqrt(1+4*a*a-4*a+8*m))/2;
            if(floor(b) == b && a < b)
                std::cout <<a <<" " <<(int)b <<"n";
        }
    }
    return 0;
}