Tóm tắt đề bài

Gọi số \(X\) là số đặc biệt nếu mọi chữ số của \(X\) đều thuộc tập \(\{1,3,5,7,9\}\). Liệt kê tất cả số đặc biệt và sắp tăng dần được dãy \(A\).
Cho \(N\) (\(1 \le N \le 10^{18}\)), hãy tìm số đặc biệt thứ \(N\) trong dãy \(A\).

Phân tích

• Với độ dài \(k\) chữ số, mỗi vị trí có \(5\) lựa chọn \(\Rightarrow\) có đúng \(5^k\) số đặc biệt độ dài \(k\).
• Dãy \(A\) khi sắp tăng dần sẽ có tính chất:
  • Tất cả số 1 chữ số (5 số) đứng trước số 2 chữ số, …
  • Trong cùng độ dài \(k\), thứ tự tăng dần trùng với thứ tự từ điển theo các chữ số (vì các số đều có cùng số chữ số).
• Vì \(N\) rất lớn (\(10^{18}\)), không thể sinh dãy. Ta cần “đánh số” trực tiếp.

Ý tưởng then chốt: ánh xạ sang biểu diễn cơ số 5

Xem mỗi số đặc biệt độ dài \(k\) như một “xâu” gồm \(k\) ký tự, mỗi ký tự thuộc tập 5 phần tử theo thứ tự tăng:
[
\text{digits} = [1,3,5,7,9]
]
Nếu đánh số các xâu độ dài \(k\) từ \(0\) đến \(5^k-1\) theo cơ số 5, mỗi chữ số cơ số 5 (từ \(0..4\)) sẽ ánh xạ tương ứng sang một chữ số trong digits.

Vấn đề còn lại:

1. Xác định độ dài \(k\) sao cho số thứ \(N\) nằm trong nhóm độ dài \(k\).
2. Tính chỉ số trong nhóm: \(idx\) (0-based), rồi đổi \(idx\) sang cơ số 5 với đúng \(k\) chữ số.

Hướng giải quyết

Bước 1: Tìm độ dài \(k\)

Duyệt \(k = 1,2,3,\dots\) và trừ dần số lượng phần tử từng nhóm:

• Nhóm độ dài \(k\) có \(cnt = 5^k\) số.
• Nếu \(N > cnt\) thì \(N \leftarrow N - cnt\) và tăng \(k\).
• Ngược lại, số cần tìm thuộc nhóm độ dài \(k\).

Lưu ý:

• \(5^{27} \approx 7.45 \times 10^{18}\) nên với \(N \le 10^{18}\) thì \(k \le 27\). Duyệt tuyến tính theo \(k\) là rất nhỏ.

Bước 2: Đổi chỉ số trong nhóm sang số đặc biệt

• Sau bước 1, ta có \(N\) nằm trong nhóm độ dài \(k\) và \(1 \le N \le 5^k\).
• Đặt \(idx = N - 1\) (0-based).
• Viết \(idx\) trong cơ số 5 với đúng \(k\) chữ số (có thể lấy từ phải sang trái):
  • Lặp \(i = 1..k\):
    • \(d = idx \bmod 5\) (thuộc \(0..4\))
    • chọn chữ số thật là digits[d]
    • \(idx \leftarrow \lfloor idx/5 \rfloor\)
• Vì ta lấy từ chữ số thấp lên, cần đảo lại (hoặc xây từ cuối về đầu).

Ví dụ nhanh

\(N=8\):

• Nhóm \(k=1\): \(5\) số, còn \(N=3\) trong nhóm \(k=2\).
• \(idx = 2\). Cơ số 5 với \(k=2\): 02 \(\Rightarrow\) chữ số: 1 và 5 \(\Rightarrow\) 15.

Độ phức tạp

• Thời gian: \(O(k)\) với \(k \le 27\) \(\Rightarrow\) coi như \(O(1)\).
• Bộ nhớ: \(O(1)\) (không tính chuỗi kết quả, tối đa 27 ký tự).

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    unsigned long long N;
    cin >> N;

    // digits theo thứ tự tăng
    const char digits[5] = {'1', '3', '5', '7', '9'};

    // Bước 1: tìm độ dài k
    unsigned long long pow5 = 1;
    int k = 0;
    while (true) {
        k++;
        // pow5 = 5^k (cẩn thận tràn: nhưng k <= 27 cho N<=1e18 nên ull đủ)
        pow5 *= 5ULL;

        if (N > pow5) {
            N -= pow5;
        } else {
            break;
        }
    }

    // Bước 2: idx = N-1, đổi sang cơ số 5 với đúng k chữ số
    unsigned long long idx = N - 1;
    string ans(k, '0');
    for (int i = k - 1; i >= 0; i--) {
        int d = (int)(idx % 5ULL);  // 0..4
        ans[i] = digits[d];
        idx /= 5ULL;
    }

    cout << ans << "\n";
    return 0;
}