题目链接
题意：求化简后的分子之和。
题解：每次先把奇数加上，剩下偶数除以2，继续上面操作知道没有剩下数或是除以2的次数等于k。
下面时AC代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define int long long
signed main()
{
int t;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
int ans=0;
int coun=0;
int x=(1+n)*n/2;
int nn=n;
while(coun<k&&x>0)
{
int kk=x;
if(nn%2==0)
{
ans+=x/(nn+1)*(nn/2);//这里一定要注意乘的顺序，如果是x*(nn/2)/(nn-1)的话也就是最大1e9*1e18,很大，会爆long long，而调整次序后不会出现这个问题，下面也是这个道理
x=x/(nn+1)*(nn/2+1)/2;
nn/=2;
}
else if(nn%2!=0)
{
ans+=x/nn*(nn/2+1);
x=x/nn*(nn/2)/2;
nn/=2;
}
coun++;
}
cout<<ans+x<<endl;
}
return 0;
}
下面是一个WA2的代码:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define int unsigned long long
signed main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
int ans=0;
int coun=0;
int x=(1+n)*n/2;
while(coun<k&&x>0)
{
int kk=x;
int nn=(-1+sqrt(1+8*kk))/2;//1 - nn
//cout<<nn<<"-->"<<endl;
if(nn%2==0)//是偶数的话
{
ans+=x/(nn+1)*(nn/2);
x=x/(nn+1)*(nn/2+1)/2;
}
else if(nn%2!=0)
{
ans+=x/nn*(nn/2+1);
x=x/nn*(nn/2)/2;
}
coun++;
//cout<<x<<"-->"<<endl;
}
int testans=0;
// for(int i=1;i<=n;i++)
// {
// int x=i;
// int coun=0;
// while(x%2==0&&coun<k)
// {
// x/=2;
// coun++;
// }
// testans+=x;
// }
cout<<ans+x<<endl;
//cout<<testans<<"==>"<<endl;
}
return 0;
}
这里nn是用 sqrt求的，精度有问题所以直接用nn/2的话会更好。
