第一想法居然是用树状数组打表,果然我的思想还是太暴力了么(捂脸
好吧,这道题其实也就是在解方程
$$ sum(l,r) = (l+r)(l-r+1)/2 = m$$
$$(l+r)(l-r+1) = 2m$$
$$ \begin{equation}\left\{\begin{array}{lr}k1 = r-l+1\\k2 = l+r\end{array}\right.\end{equation}$$
解得
$$ \begin{equation}\left\{\begin{array}{lr}l = (k2-k1+1)/2\\r = (k1+k2-1)/2\end{array}\right.\end{equation}$$
当$l,r$一奇一偶时才有自然数解。($l=r$时也成立,但不符合题目要求,求解得$k1 \doteq 1$)
代码如下
#include <bits/stdc++.h>
using namespace std;
int m;
int main() {
ios::sync_with_stdio(false);
cin>>m;
for(int k1=sqrt(2*m);k1>1;--k1)
if(((2*m)%k1 == 0) && ((k1 + (m*2)/k1)%2)) {
int k2 = (2*m)/k1;
cout<<(k2-k1+1)/2<<" "<<(k1+k2-1)/2<<endl;
}
return 0;
}
其实仔细想想数论题就应该想一想列一列方程
参考资料