学步园

题目连接：http://acm.fzu.edu.cn/problem.php?pid=1988

这个题的关键在于计算G(x)

G(x)的计算方法很奇特，我现在也不能证明

在计算出G(x)之后我们就可以使用二分来寻找答案了

我的代码：

#include<stdio.h><br /> #include<math.h></p> <p>__int64 Count(__int64 n)<br /> {<br /> __int64 i;<br /> __int64 ans=0;<br /> __int64 m=(int)sqrt((double)(n));<br /> for(i=1;i<=m;i++)<br /> {<br /> ans+=n/i;<br /> }<br /> return (ans<<1)-m*m;<br /> }</p> <p>int main()<br /> {<br /> __int64 m,l,r,mid,t,T=1;<br /> bool flag;<br /> scanf("%I64d",&t);<br /> while(t--)<br /> {<br /> flag=true;<br /> scanf("%I64d",&m);<br /> l=1,r=55592640;<br /> while(l<=r)<br /> {<br /> mid=(l+r)>>1;<br /> __int64 temp=Count(mid);<br /> if(temp>m)<br /> r=mid-1;<br /> else if(temp<m)<br /> l=mid+1;<br /> else<br /> {<br /> flag=false;<br /> printf("Case %I64d: %I64d/n",T++,mid);<br /> break;<br /> }<br /> }<br /> if(flag)<br /> printf("Case %I64d: impossible!/n",T++);<br /> }<br /> return 0;<br /> }