洛谷P8039题解

Ginger_he · 2022-01-15 19:37:16 · 题解

题目描述

求出所有的和为 N 的长度 \geqslant 2 的连续自然数段。

题解

设这一段的最小值为 l，最大值为 r。
由等差数列求和公式有 \dfrac{(l+r)(r-l+1)}{2}=N。
将 2 乘到右边有 (l+r)(r-l+1)=2N。
对 2N 进行质因数分解，不妨假设 2N=x\times y(x\geqslant y)。
因为 l 和 r 均为正整数，因此 l+r\geqslant r-l+1，

这时候只需要判断 x 和 y-1 是否相等以及奇偶性是否相同即可。
时间复杂度 \Theta(\sqrt{2N})。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,x;
int main()
{
    scanf("%lld",&n);
    if(n==1)
        return 0;//特判
    m=sqrt(n<<=1);
    for(ll i=1;i<=m;i++)//根号枚举因数
    {
        if(n%i)
            continue;
        x=n/i;
        if((x%2)!=(i%2)&&x-i+1!=x+i-1)//符合条件
            printf("%lld %lld\n",x-i+1>>1,x+i-1>>1);
    }
    return 0;
}