自动搬运

查看原文

来自洛谷，原作者为

	Ginger_he .

搬运于2025-08-24 22:35:24，当前版本为作者最后更新于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$， $\begin{cases}l+r=x\\r-l=y-1\end{cases}$
这时候只需要判断 $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;
}