Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## log(1<<64)*20的复杂度怎么能tls呢？！

Posted by highkobe at 2009-04-08 00:00:05 on Problem 3725
```#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<queue>
#include<set>
using namespace std;
const int INF=0x7fffffff;
const double eps=(1.0e-9);
const double PI=atan2(0.0,-1.0);
typedef long long int64;
int64 m,k;
int64 dig[20],n;
int64 base[20];
int64 solve(int64 now)
{
int64 dit[20],i;
int64 cur=now,d[20];
if(now<m)
return 0;
for(i=1;;i++)
{
dit[i]=cur%10;
cur/=10;
if(cur==0)
break;
}
int nn=i;
//intf("n----%d nn----%d\n",n,nn);
d[n]=m;
for(i=n+1;i<=nn;i++)
d[i]=10*d[i-1];
for(i=n-1;i>=1;i--)
{
d[i]=d[i+1]/10;
}
int64 ans=0;
for(i=nn;i>=1;i--)
{
if(now<d[i])
ans+=now-base[i]+1;
else
{
ans+=d[i]-base[i];
if(d[i]<=m)
ans++;
}
}
return ans;
}
int main()
{
int64 bases;
int64 i;
base[1]=1;
for(i=2;i<=20;i++)
base[i]=10*base[i-1];
for( bases=1,i=1;i<=18;bases*=10,i++)
;
while(cin>>k>>m)
{
int64 now=m;
for(i=1;;i++)
{
dig[i]=now%10;
now/=10;
if(now==0)
break;
}
n=i;
int64 r,l,mid,flag=0,ans;
l=0;
r=9*bases;
while(l<=r)
{
mid=(l+r)/2;
int64 now=solve(mid);
if(now==k)
{
flag=1;
ans=mid;
break;
}
else if(now<k)
l=mid+1;
else
r=mid-1;
}
if(flag==1)
cout<<ans<<endl;
else
cout<<0<<endl;
}
return 0;
}

```

Followed by: