当前位置: 代码迷 >> 综合 >> 洛谷 P2022 有趣的数
  详细解决方案

洛谷 P2022 有趣的数

热度:7   发布时间:2024-01-19 02:48:41.0

题目描述

让我们来考虑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。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

数论~

神奇的解法~


#include<cstdio>
#include<iostream>
using namespace std;
#define ll long longll n,m,k,cnt,tot=1,f[21],s[21];void get(ll x)
{ll t=0; while (x){s[++t]=x%10;x/=10;tot*=10;}tot/=10;for(int i=1;i<=t;i++) f[i]=s[t-i+1];cnt+=t-1;for(int i=t;i>=1;i--){ll sum=0;for(int j=1;j<=i;j++)if(j!=1)sum*=10,sum+=f[j];else sum*=10,sum+=f[j],sum-=1;cnt+=sum;} 
}   int main()
{scanf("%lld%lld",&k,&m);get(k);if(cnt>=m || (k==tot && cnt<m-1)){cout<<0<<endl;return 0;}ll p=k-tot,c=k;for(;cnt<m-1;){p*=10;c*=10;cnt+=p;}n=max(k,c-(cnt-m+2));printf("%lld\n",n);return 0;
}


  相关解决方案