Educational Codeforces Round 1 A. Tricky Sum

原题: http://codeforces.com/contest/598/problem/A

---

题目大意: 给一个数字n, 求1…n的合, 其中如果遇到2的倍数的数,要当负数处理.

---

分析: 直接求O(n) 会超时, 所以会想到求和公式.

通过观察可以发现, 给一个n, 我们可以:

1. 求1到n的合, 用等差数列求和公式.
2. 找到1到n中,有多少个2的倍数, 用对数公式, 这里注意, 1也是, 所以求完log后要用flooring求包含几个2的倍数后, 要加上1.
3. 用公式
4. 减去两杯的上面公式的结果就是答案了.

public class TaskA {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        for (int i = 0; i < n; i++) {
            out.printLine(solve(in.readLong()));
        }
    }
    public long solve(long n) {
        long sum = n+(n)*(n-1l)/2l;
        long numOfPowerOf2 = (long)Math.floor(log(n,2))+1;
        long minus = (long)Math.pow(2,(numOfPowerOf2))-1;
        return sum - 2*minus;
    }
    public long log(long x, long base)
    {
        return (long) (Math.log(x) / Math.log(base));
    }
}