* **Làm thế nào để xác định số chữ số của số chứa chữ số thứ $n$ trong dãy số liên tiếp?**
Nếu muốn tìm được chữ số thứ $n$ khái quát thì chúng ta cần tìm được số chứa chữ số thứ $n$ có bao nhiêu chữ số, gọi số chữ số chứa số thứ $n$ là $x$
* **Làm thế nào để xác định chính xác số chứa chữ số thứ n và có $x$ chữ số?**
* **Làm thế nào để xác định chính xác số chứa chữ số thứ n và vị trí của chữ số thứ n trong số đó?**
Nếu muốn tìm số chữ số của số chữ chữ số thứ n thì ta có thể liệt kê các miền giá trị của các số có số lượng chữ số là $x$, ví dụ:
* $x=1:$ có $1 \rightarrow 9$ là những số có $x=1$ chữ số $\Longrightarrow$ với $x = 1$ thì có $9$ số thỏa mãn và mỗi số có $x = 1$ chữ số, vậy với $x = 1$ thì có $9$ chữ số.
* $x=2:$ có $10 \rightarrow 99$ là những số có $2$ chữ số $\Longrightarrow$ với $x = 2$ thì có $90$ số và mỗi số có $2$ chữ số, vậy với $x = 2$ thì có $90 \times 2$ chữ số.
* $x=3:$ có $100 \rightarrow 999$ là những số có $3$ chữ số $\Longrightarrow$ với $x = 3$ thì có $900$ số và mỗi số có $3$ chữ số, vậy với $x = 3$ thì có $900 \times 3$ chữ số.
* $x=4:$ có $1000 \rightarrow 9999$ là những số có $4$ chữ số $\Longrightarrow$ với $x = 4$ thì có $9000$ số và mỗi số có $4$ chữ số, vậy với $x = 4$ thì có $9000 \times 4$ chữ số.
* Và cứ thế....
$\Longleftrightarrow$ Với số có $x$ chữ số thì ta có $9\times x \times 10^{x-1}$ chữ số thuộc các số thỏa mãn điều kiện có $x$ chữ số.
Gọi $f(x)=9\times x \times 10^{x-1}$
Nếu số ở vị trí thứ $n$ có $x$ chữ số thì nó phải nhiều hơn số lượng chữ số tại $x – 1$, $x – 2$, $x – 3$, $...$, $1$ chữ số.
Tức là $n > f(x-1)+ f(x-2)+⋯+ f(1)$.
Ví dụ :
$n = 191$
$123456789^1$$10111213141516171819202122^2$ $....1$```0```$0101102...^3$
* Dãy số có mũ $1$ là số có $1$ chữ số và $f(1) = 9$
* Dãy số có mũ $2$ là số có $2$ chữ số và $f(2) = 80$
* Dãy số có mũ $3$ là số có $3$ chữ số và $f(3) = 2700$
* Chữ số ``0`` này là chữ số thứ $191$
Như ví dụ trên ta nhận thấy $n$ phải thỏa mãn $n> f(1)+f(2)$
Tức là số lượng chữ số cần thiết để cho số chứa số cần tìm có $x$ chữ số phải là
$$
\sum_{i=1}^{x-1} f(i)
$$
Khi đó mảng mà chúng ta tìm kiếm nhị phân sẽ có giá trị lần lượt và ngăn cách bởi dấu ```,``` là:
$$
f(1),f(1)+f(2),f(1)+f(2)+f(3),f(1)+f(2)+f(3)+f(4),…
$$
Gọi mảng này là mảng $scs$ để tiện cho việc gọi tên.
$$
scs[k] = \sum_{i=1}^{k-1} f(i)
$$
Khi tìm ra được số đó có bao nhiêu chữ số thì ta sẽ dùng công thức:
$$
num=\frac{n-scs[x-1]-1}{x}+10^{x-1}
$$
Với:
* $num:$ số chứa chữ số cần tìm.
* $n:$ vị trí số thứ $n$ cần tìm
* $x:$ số lượng chữ số của số chứa chữ số cần tìm.
* $scs:$ .....
**Giải thích công thức:**
$n- scs[x-1]-1$ tức là vị trí của chữ số cần tìm trong các số có $x$ chữ số.
**Gọi** $p=n- scs[x-1]-1$
Khi ta biết được vị trí của chữ số cần tính từ số đầu tiên có $x$ chữ số,thì ta chỉ cần lấy vị trí đã tìm được chia nguyên cho $x$ là ra vị trí của số chứa số cần tìm.
$\Longrightarrow$ $num=\frac{p}{x}$
Nhưng vậy là chưa đủ vì $\frac{p}{x}$ chỉ mới là vị trí nếu muốn tìm chính xác số đó thì ta cần $+$ vị trí với số bắt đầu nữa
Số bắt đầu thỏa mãn có $x$ chữ số là: $10^{x-1}$.
$\Longrightarrow$ $num=\frac{p}{x}+10^{x-1}$
Khi có được số chứa chữ số cần tìm thì ta chỉ cần biết được vị trí của chữ số cần tìm trong số chứa nó thì ta có thể đưa ra đáp án.
Gọi vị trí của chữ số cần tìm trong số chứa nó là $id$.
$\Longrightarrow$ $id \equiv p$ (mod $x$)
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 30;
long long k, scs[maxn], f[maxn], p[maxn];
// p[i] = 10 ^ i
void init(){
p[0] = 1;
for(int i = 1; i <= 18; i++)
p[i] = p[i - 1] * 10LL;
for(int x = 1; x <= 18; x++)
f[x] = 9LL * x * p[x - 1];
for(int i = 1; i <= 18; i++)
scs[i] = scs[i - 1] + f[i];
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define NAME "WS"
if(fopen(NAME".INP", "r")){
freopen(NAME".INP", "r", stdin);
freopen(NAME".OUT", "w", stdout);
}
cin >> k;
init();
// tìm số lượng chữ số của số chứa số thứ k
int x = lower_bound(scs + 1, scs + 19, k) - scs;
// vị trí của số thứ k trong tập những số có x chữ số
long long tmp = k - scs[x - 1] - 1;
// số chứa chữ số thứ k
long long num = tmp / x + p[x - 1];
// vị trí của chữ số thứ k trong số chứa nó (num)
int pos = tmp % x;
// chuyển thành string để dễ lấy chữ số thứ k hơn
string number = to_string(num);
cout << number[pos];
return 0;
}
```
Vinhzn08
Created at
2 likes