XUPT-D

/*
     泰泰学长又来玩数字了，泰泰学长想让你帮他求1-n的和，但是这次的求和可不是简单的1+2+...+n。这次的求和是这样的，如果加到一个数字是2的指数倍，那就不加，反而减掉这个数。
    比如 n = 4：-1-2+3-4 = -4。
    说明：其中1,2,4都是2的指数倍。
Input
    第一行是总询问数 T，接下来T行，每行一个 n，(1<=T<=100)(1<=n<=10^9)
Output

    输出对应的结果
Sample Input
    2
    4
    1000000000
Sample Output

    -4
    499999998352516354
*/

可以借助等比数列和位移求解（1+n）*n/2 - 2*（2的等比数列和）；
2的等比数列和可以借助位移求解

 1 #include <cstdio>

 2 #include <cmath>

 3 typedef long long LL;

 4 using namespace std;

 5 int main(){

 6     int t;

 7     LL n;

 8     scanf("%d", &t);

 9     while(t--){

10         scanf("%lld", &n);

11         LL sum = (1+n)*n/2;

12         int count = 1;

13         while(n >>= 1){

14             count++;

15         }

16         LL temp = 2 * ((LL)pow(2, count) - 1);

17         sum = sum - temp;

18         printf("%lld\n", sum);

19     }

20     return 0;

21 }

巴特西

XUPT-D

最新文章

热门文章