题解 P2022 【有趣的数】

· · 题解 

   由于答案可能非常大，所以这道题显然不能用枚举，即便用二分，时间复杂度{O[N(logN)^2]}也特别大。我们可以设所有字典序比K小的数中的第M-1个为X，N就等于K与X的最大值，怎么求X呢？[delete]当然是枚举。[/delete]我们把所有字典序比K小的数分成无穷大个集合。集合Ai里的任意两个数j,k，都满足i=floor(log10(j))=floor(log10(k))（floor(a)表示取a的整数部分，log10(a)表示以10为底，以a为真的对数值），其中最大值为ai。我们可以发现，设K的左数第i位是pi,qi=∑pj\*(i-j+1)(1<=j<=i),当j<=log10(K)，|Aj|=qj-1，aj=qj-1；当j>log10(K)，|Aj|=|A(j-1)|\*10（请读者自己证明）。由此我们可求出X所在集合Ai，且X=ai+[M-∑|Aj|(1<=j<=i)]-1。求X所在集合的时间复杂度和求出X所在集合后求X的值的时间复杂度均为O[log10(N)]，总的时间复杂度为O[log10(N)]。

#include<iostream> 
using namespace std;
long long k,m,i,number=0,n;
int main ()
{
    cin>>k>>m;
    for (i=1;i<=k;i*=10)
    number+=k/i-i+1;
    number--;
    if (number>=m||k-(i/10)==0&&number<m-1)
    cout<<0;
    if (number>=m||k-(i/10)==0&&number<m-1)
    return 0;
    for (i=k-(i/10),n=k;number<m-1;i*=10,number+=i,n*=10);
    cout<<max(n-number+m-2,k);
    return 0;
}