自动搬运

查看原文

来自洛谷，原作者为

	D2T1 没复活就是似了 | 头发绿绿戴个帽帽，脑袋大大，喜欢唱唱

搬运于2025-08-24 22:06:53，当前版本为作者最后更新于2021-07-01 17:53:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$\color{blue}{\text {pwp }~{\to\textbf{My blog}\gets}}~\text{qwq}$

前置知识

$\sum\limits_{i=1}^n i = \dfrac{n(n+1)}{2}$（$n$ 为正整数）

题解

设最终答案为 $l+1$ 与 $r$，则

$$s=\sum\limits_{i=l+1}^r i = \sum\limits_{i=1}^r i-\sum\limits_{i=1}^l i $$

利用公式，得

$$s=\dfrac{r(r+1)}{2}-\dfrac{l(l+1)}{2}$$ $$\therefore 2s=r(r+1)-l(l+1)$$ $$2s=(r+l+1)(r-l)$$

所以我们可以暴力枚举 $2s$ 的因数，求出 $r+l+1$ 和 $r-l$ 的值，进而算出答案。

复杂度 $O(\sqrt{s})$。

代码

//P5077
#include <cstdio>
typedef long long ll;

int main(){
	ll s,l=0x3f3f3f3f3f3f3f3f,r;
	scanf("%lld",&s); s<<=1;//最后分解质因数的是 2s
	for(ll i=1; i*i<=s; ++i)
		if(s%i==0){
			ll j=s/i;
			if((i&1)^(j&1))//因为 r+l+1 与 r-l 奇偶性不同，所以可以在这进行判断
				if(l>j-i-1)//解二元一次方程组，取 l 的最小值
					l=(j-i-1)/2,r=(j+i-1)/2;
		}
	printf("%lld %lld",l+1,r);//记得答案是 l+1 和 r
	return 0;
}

补充

可以发现，当 $2s$ 分解出的两个因数的差越小时，$l+1$ 就越小，所以可以在循环时从大到小循环，只要求出一组答案直接结束循环，可以快 21ms。

//P5077
#include <cstdio>
#include <cmath>
typedef long long ll;

int main(){
	ll s,l=0x3f3f3f3f3f3f3f3f,r;
	scanf("%lld",&s); s<<=1;
	for(ll i=sqrt(s); i; --i)
		if(s%i==0){
			ll j=s/i;
			if((i&1)^(j&1)){
			    printf("%lld %lld",(j-i+1)/2,(j+i-1)/2);
			    return 0;
			}
		}
}