题解 | F题 Sum of Numerators

看到没人写详细的题解，新手小白想来写个题解锻炼一下自己qwq，代码优化差，这里只是提供一个思路，写的不好请见谅。

F题是一个数学题目，相信大家都读过题目了我就不在多做赘述，关键在于怎么把代码优化。

链接点这里

第一个思路肯定是暴力累加，但这样的话光n就有1e9，毛估估也要O(nlogn)，肯定是不行的，这时候就要开始找规律了，我们首先想到，如果是奇数（也就是所有数取一半）的话可以直接累加，所以用（首项+末尾项）*（（末尾项-首项）/公差+1）可以直接求和，一半的工程就完结了（不过只是少了一半的复杂度qwq）。

然后我们看到偶数部分，2，4，6，8，10，12...我们再在偶数部分取一半，取2，6，10...然后我们把这些数除以2，惊人的发现，这些数变成了1，3，5...同理，剩下数再取一半，然后除4，又变成了奇数串，然后循环往复，这道题的优化思路就诞生了，复杂度在O(log(n))吧。

当然，上面考虑的情况只是k取无穷大，也就是2能除尽的情况，那如果除不尽呢？也好办，只要在计算完奇数串和之后末尾乘上2的若干次幂就好了。

sum+=((1+d)*((d-1)/2+1)/2)*(max(1ll,power(i-k-1)));

这是核心代码，d表示奇数项最后一项，i表示第几次求和。

完整代码如下：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll power(ll x){
	ll ans=1;
	for (ll i=1;i<=x;i++){
		ans*=2;
	}
	return ans;
}
ll logger(ll x){
	ll cnt=0;
	while (x>0){
		x=x/2;
		cnt++;
	}
	return cnt-1;
}
void work(){
	ll n,k;
	ll sum=0;
	scanf("%lld%lld",&n,&k);
	for (int i=1;i<=logger(n)+1;i++){	
		ll d=n/power(i-1);
		if (d%2==0) d--;
		sum+=((1+d)*((d-1)/2+1)/2)*(max(1ll,power(i-k-1)));	
	}	
	printf("%lld\n",sum);
}
int main(){
	int _;
	scanf("%d",&_);
	while (_--){
		work();
	}
	return 0;
}