十九届浙大城院程序设计竞赛 F.Sum of Numerators(数学/找规律)

题目链接 https://ac.nowcoder.com/acm/contest/31533/F

 

示例1

输入

2
5 0
5 1

输出

15
12

 

解析： 

        数学思维题。枚举结果来找规律，然后利用等差数列求和公式来求出结果。

 

C++代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    int t, n, k, res;
    cin >> t;
    while(t--){
        cin >> n >> k;
        res = n * (n + 1) / 2; //先用等差数列求和公式求出总和
        while(n and k){
            n /= 2;   //会被约分的数字个数每次都是总长的一半
            --k;    //每次被约分，2的次数减一
            res -= (n * (n + 1) / 2);  //找规律，可知每次被约分掉的总和是 等差数列求1到被约分掉的数字个数之和
        }
        cout << res << "\n";
    }
    return 0;
}