P5722 【深基4.例11】数列求和 的不寻常做法

PengDave · 2024-04-27 18:24:54 · 题解

是时候来篇 O(\log_{2}{n}) 的题解啦。

solution

对于 1+2+3\cdots+(n-1)+n 这样的数列，我们可以将其分成奇数和偶数两部分，奇数部分项数显然是 \left \lceil \frac{n}{2} \right \rceil ，因为连续 n 个奇数相加之和等于项数的平方，所以数列中奇数相加的和为 \left \lceil \frac{n}{2} \right \rceil^{2}。至于偶数，很显然一共有 \left \lfloor \frac{n}{2} \right \rfloor 项，将每项除以 2，可得：1+2\cdots+(\left \lfloor \frac{n}{2} \right \rfloor-1)+\left \lfloor \frac{n}{2} \right \rfloor 。设 f(x) 表示 1+2+3\cdots+(x-1)+x 的和，则可得：

code

#include<iostream>
using namespace std;
int f(int x){
    if(x==0){
        return 0;
    }
    if(x==1){
        return 1;
    }
    return 2*f(x/2)+((x+1)/2)*((x+1)/2);
}
int main(){
    int n;
    cin>>n;
    cout<<f(n)<<endl;
    return 0;
}