Codeforces 598A Tricky Sum 技巧求和

题目地址:http://codeforces.com/problemset/problem/598/A
这道题目本来一开始是想要搞暴力的,但是第一个就超时。不得已换了个数学方法。
首先用小学生都会的数列求和:(首项+末项)*项数/2 把从1…n的和算出来,然后计算出不大于n的2的幂次共有多少个,用等比数列求和公式求出它们的和,减去两倍即可。
上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<algorithm>
using namespace std;
long long try2(long long n){ //函数try2就是计算从1到n之间所有不大于n的2的幂次之和,可结合等比数列求和公式推导后再领悟,不懂可以看下面或者评论我博客。
    long long m2=1;
    while(m2<=n)m2*=2;
    return m2-1;
}
void process(){
    long long n;
    cin>>n;
    cout<<((1+n)*n/2-2*try2(n))<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--)process();
}

其实做这道题是要数学功底的。。。我还是把具体的推导过程说一下好了。我们想要求出小于n的所有2的幂次方项之和,根据等比数列求和公式可知:$$2^0+2^1+2^2+…+2^n=2^{n+1}-1$$所以我们只要找到最大的小于n的2的幂次再乘2减1就可以了。具体代码可参见函数try2()。

发表评论

电子邮件地址不会被公开。 必填项已用*标注