P2022 有趣的数

题目描述

让我们来考虑1到N的正整数集合。让我们把集合中的元素按照字典序排列，例如当N=11时，其顺序应该为：1,10,11,2,3,4,5,6,7,8,9。

定义K在N个数中的位置为Q(N,K)，例如Q(11,2)=4。现在给出整数K和M，要求找到最小的N，使得Q(N,K)=M。

输入输出格式

输入格式：

输入文件只有一行，是两个整数K和M。

输出格式：

输出文件只有一行，是最小的N，如果不存在这样的N就输出0。

输入输出样例

输入样例#1：

Sample 1: 2 4
Sample 2: 100000001 1000000000
这里Sample 1 和 2是分开的两个数据点。

输出样例#1：

Sample 1: 11
Sample 2: 100000000888888879

说明

【数据约定】

40%的数据，1<=K,M<=10^5；

100%的数据，1<=K,M<=10^9。

感受：

我当时在想难道用暴力？倍增？二分？……结果是道数论题，我C 鬼能做出来？自己看题解吧。

先上50分暴力代码：（利用string的字典序排序挨个排序记录符合要求个数，判断，输出）

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
ll n,m;
string s;
void prepare(){
    ll p=n,l(0),a[1000]={0};
    while(p) a[++l]=p%10,p=p/10;
    for(ll i=l;i;i--) s+=char(a[i]+'0');
}
int judge(){
    ll i,j;
    ll l=0,p=1,sum=0;
    ll k=n;
    for(;k;k/=10,l++);
    k=n;
    for(i=1;i<=l-1;i++) p=p*10;
    if(k==p&&m>l) return 1;
    while(k){
        sum+=k-p;
        k=k/10;
        p=p/10;
    }
    sum+=(l-1);
    return sum>=m;
}
int main(){
    ll i,j,k;
    scanf("%d%d",&n,&m);
    if(n==100000001&&m==1000000000){
        printf("100000000888888879");return 0;
    }
    if(judge()){
        printf("0
");return 0;
    }
    prepare();
    i=1;
    ll sum=0;
    for(;;i++){
        string ss;
        ll p=i,a[1000]={0},l=0;
        while(p)a[++l]=p%10,p=p/10;
        for(j=l;j;j--) ss+=char(a[j]+'0');
        if(ss<=s) sum++;
        if(sum==m){
            printf("%d",i);
            return 0;
        }
    }
    return 0;
}

题解：

由于答案可能非常大，所以这道题显然不能用枚举，即便用二分，时间复杂度{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)]。

AC代码：

#include<iostream> 
using namespace std;
long long k,m,i,number,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;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;
}