题目地址：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()。