Nhân đang tập đếm các số 1, 2, 3, 4, 5, ... Nhận thấy việc này quá dễ, cộng với việc vừa mới học được phép nhân, Nhân quyết định đếm các số chính phương (là những số bằng một số nguyên nhân với chính nó) và viết chúng ra giấy và thu được một dãy dài có các số đầu tiên là 149162536... Nhân muốn biết chữ số thứ k của dây là bao nhiêu. Các bạn hãy tỉnh giúp Nhân nhé. Input: Một số nguyên dương duy nhất k (1 k 10^9). Output: Chữ số thứ k của dây. Sample: Input 10 Output 4 Notes Các chữ số đầu tiên của dây là 14916253649... C++

#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int f[17] = {0, 3, 6, 22, 68, 217, 683, 2163, 6837, 21623, 68377, 216228, 683772, 2162278, 6837722, 21622777, 68377224};
ull p10(int n) {
    if (n == 0) return 1;
    ull res = 1;
    for (int i = 1; i <= n; i++) res *= 10;
    return res;
}
int main() {
    int k, n = 1;
    cin >> k;
    while (k >= n*f[n]) {
        k -= n*f[n];
        n++;
    }
    if (k == 0)
        cout << ((ull)(sqrt(p10(n - 1) - 1))*(ull)(sqrt(p10(n - 1) - 1))) % 10; 
    else if (k % n == 0) cout << to_string((ceil(sqrt(p10(n - 1))) + k / n - 1)*(ceil(sqrt(p10(n - 1))) + k / n - 1))[n - 1];
    else cout << to_string((ceil(sqrt(p10(n - 1))) + k / n)*(ceil(sqrt(p10(n - 1))) + k / n))[k % n - 1];
    return 0;
}