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. 用公式Screen Shot 2016-02-27 at 11.59.02 AM
  4. 减去两杯的上面公式的结果就是答案了.