P5077 Tweetuzki 爱等差数列
D2T1
·
·
题解
\color{blue}{\text {pwp }~{\to\textbf{My blog}\gets}}~\text{qwq}
前置知识
## 题解
设最终答案为 $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})$。
## 代码
```cpp
//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。
```cpp
//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;
}
}
}
```