題目連結:Sprout Online Judge No. 840
題目敘述
你有一個大整數 012345678910111213141516171819202122…
也就是說,這個大整數是把所有非負整數依序串在一起。
現在,給你 n、k,請你輸出,在這個大整數中,由左至右第 n 次出現數字 k,是出現在第幾個位置?
位置從 1 開始算,並保證 k 是介於 0 到 9 之間的整數。
注意到,因為這個大整數太特別了,你定義這個大整數的第一位是 0 。
n≤10^12,0≤k≤9
想法
數字這麼大,一定是二分搜尋,找出最後一個含有數字 k 小於 n 的數字。
而求在 num 之前有多少數字 k 的方法則放在 HackMD(因為比較好寫數學式)。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
// just for 0
ll countDigit(ll n){
if(n<1) return 1;
ll high=n,tp=0,cur=0,low=0,base=1,ret=0;
while(high>0){
high=n/(10*base);
tp=n%(10*base);
cur=tp/base;
low=tp%base;
if(cur==0){
ret+=(high-1)*base+low+1;
}else{
ret+=high*base;
}
base*=10;
}
return ret+1;
}
// only for 1~9
ll countDigit(ll n,ll k){
if(k==0) return countDigit(n);
ll high=n,tp=0,cur=0,low=0,base=1,ret=0;
while(high>0){
high=n/(10*base);
tp=n%(10*base);
cur=tp/base;
low=tp%base;
if(cur==k){
ret+=high*base+low+1;
}else if(cur<k){
ret+=high*base;
}else{
ret+=(high+1)*base;
}
base*=10;
}
return ret;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
ll n,k;
cin>>n>>k;
ll l=0,r=1000000000000000000;
while(r-l>1){
ll mid=l+r>>1;
if(countDigit(mid,k)>=n){
r=mid;
}else{
l=mid;
}
}
ll ans=countDigit(l);
for(int i=1;i<=9;++i){
ans+=countDigit(l,i);
}
ll ctd=countDigit(l,k);
l++;
vector<int> ns;
while(l>0){
ns.emplace_back(l%10);
l/=10;
}
reverse(ns.begin(),ns.end());
// search the nth k
for(int i=0;i<ns.size();++i){
if(ctd==n) break;
if(ns[i]==k) ctd++;
ans++;
}
cout<<ans<<"\n";
}