Tricky Sum - Educational Codeforces Round 1 A

http://www.chenguanghe.com/educational-codeforces-round-1a-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 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));

    }