第一想法居然是用树状数组打表,果然我的思想还是太暴力了么(捂脸

好吧,这道题其实也就是在解方程

$$ 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;
}

其实仔细想想数论题就应该想一想列一列方程


参考资料

Last modification:March 5th, 2020 at 12:18 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏