Hiểu bài toán

Bài toán yêu cầu tìm số nguyên dương nhỏ nhất lớn hơn hoặc bằng N (0 ≤ N ≤ 10^7) sao cho số đó có thể biểu diễn dưới dạng tổng các lũy thừa của cơ số k (2 ≤ k ≤ 10^7) mà không có lũy thừa nào bị lặp lại. Nói cách khác, số đó phải có dạng một số nhị phân (base-k) chỉ chứa các chữ số 0 và 1 khi biểu diễn dưới cơ số k. Nếu N đã thỏa mãn điều kiện này, kết quả là N. Ngược lại, cần tìm số tiếp theo có dạng 'chỉ gồm 0 và 1' trong hệ cơ số k.

Các cách tiếp cận

Cách Quay lui (Backtracking) - Sinh các tổng

#include <iostream>
#include <vector>
using namespace std;

long long n,k,x;
long long res = 1e18,chia_du = 1e9+7;
vector<long long> a;
bool check = false;

void Try(int i,long long sum){
    if(sum >= n){
        res = min(res,sum);
        return;
    }
    if(i == x){
        return;
    }
    Try(i+1,(sum+a[i])%chia_du);
    Try(i+1,sum%chia_du);
}

int main(){
    cin>>n>>k;
    long long tmp = 1,s = 0;
    while(tmp <= n){
        s += tmp;
        a.push_back(tmp);
        tmp *= k;
    }
    if(s < n){
        a.push_back(tmp);
    }
    x = a.size();
    Try(0,0);
    cout<<res;
    return 0;
}

• Time Complexity: O(2^M) với M là số lượng số mũ (khoảng 24 nếu k=2, N=10^7)
• Space Complexity: O(M)

Cách tiếp cận này sinh ra tất cả các tổng có thể tạo thành từ các lũy thừa của k nhỏ hơn hoặc bằng N (và bù một số lũy thừa lớn hơn nếu tổng các số nhỏ hơn chưa đủ). Nó sử dụng đệ quy để thử hoặc chọn hoặc không chọn mỗi lũy thừa.

1. Tạo danh sách các lũy thừa: 1, k, k^2, ... cho đến khi tổng của chúng vượt quá N.
2. Duyệt qua từng lũy thừa, thử hai trường hợp: cộng lũy thừa này vào tổng hiện tại hoặc bỏ qua.
3. Khi tổng >= N, cập nhật kết quả nhỏ nhất.

Lưu ý: Code mẫu có vẻ tính toán modulo sai lệch trong đệ quy (sum % chia_du), có thể gây lỗi logic nếu sum vượt quá long long, nhưng mục đích chính là sinh ra các tổng.

Cách Tìm kiếm nhị phân (Binary Search)

// Pseudocode logic based on Solution 1 structure
// Hàm kiểm tra một số x có phải là số đặc biệt không
bool is_special(long long x, long long k) {
    while (x > 0) {
        if (x % k > 1) return false;
        x /= k;
    }
    return true;
}

// Hàm tìm kiếm
long long solve(long long n, long long k) {
    if (n == 0) return 0;
    long long low = n, high = 2e18; // Tìm kiếm trong khoảng lớn
    long long ans = high;
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (is_special(mid, k)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return ans % (1000000007);
}

• Time Complexity: O(log(Range) * log_k(Range)) ~ O(log(10^18) * log(10^7))
• Space Complexity: O(1)

Phương pháp này tìm kiếm số lớn hơn hoặc bằng N thỏa mãn điều kiện bằng cách duyệt tuần tự các số từ N trở lên (hoặc dùng tìm kiếm nhị phân).

1. Định nghĩa hàm is_special(x, k) kiểm tra số x có phải là số đặc biệt cơ số k hay không bằng cách lấy dư lần lượt các chữ số cơ số k. Nếu chữ số nào > 1 thì không phải.
2. Dùng tìm kiếm nhị phân trong khoảng [N, Upper Bound] để tìm số đặc biệt nhỏ nhất.

Tuy nhiên, do ràng buộc k có thể lên tới 10^7, số lượng số mũ M rất nhỏ (khoảng 2-3 nếu k lớn). Dù vậy, cách này vẫn an toàn về thời gian.

Cách Giải thuật tham lam (Greedy) - Biến đổi cơ số

#include <iostream>
#include <vector>
using namespace std;

long long mod = 1e9 + 7;

long long find(long long n, long long k) {
    if (n == 0) return 0;
    long long c = n % k;
    long long newn = n / k;
    if (c == 0 || c == 1) {
        long long temp = find(newn, k);
        long long res = (temp * (k % mod)) % mod;
        res = (res + c) % mod;
        return res;
    }
    else {
        long long temp2 = find(newn + 1, k);
        long long res = (temp2 * (k % mod)) % mod;
        return res;
    }
}

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

    int n, k; cin >> n >> k;
    long long res = find(n, k);
    cout << res;

    return 0;
}

• Time Complexity: O(log_k N) (rất nhỏ)
• Space Complexity: O(log_k N) (độ sâu đệ quy)

Đây là cách tiếp cận hiệu quả nhất dựa trên logic xử lý số.

Nguyên lý: Biểu diễn N dưới cơ số k. Nếu tất cả các chữ số đều là 0 hoặc 1, N chính là câu trả lời. Ngược lại, nếu có chữ số >= 2:

1. Ta cần loại bỏ chữ số này.
2. Cách duy nhất để loại bỏ là "nhớ" (carry) sang chữ số bên trái (tức là chia hết cho k và cộng 1 vào phần nguyên).
3. Khi thực hiện carry, các chữ số ở vị trí thấp hơn (bên phải) sẽ bị đặt thành 0.
4. Vì vậy, khi gặp chữ số >= 2, ta gọi đệ quy tìm số đặc biệt cho new_n = n/k + 1. Kết quả trả về sẽ là một số có dạng 0-1 ở các vị trí cao hơn, và các vị trí thấp hơn đều là 0.
5. Nếu chữ số là 0 hoặc 1, ta giữ nguyên và tiếp tục kiểm tra các chữ số cao hơn.

Ví dụ: N=8, k=3. Biểu diễn: 22 (3). Có số 2 -> Thừa số 3 (22 / 3 = 7 dư 2). Gọi find(7+1, 3) -> find(9, 3). 9 = 100 (3) -> Thỏa mãn. Trả về 9.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Vấn đề tương đương với việc tìm số tiếp theo có dạng số nhị phân (base-k) trong hệ cơ số k.
• Nếu k lớn (k > N), duy nhất 1 là số đặc biệt. Nếu N=1, trả về 1. Nếu N > 1, trả về k.
• Cách tiếp cận tham lam biến đổi cơ số (phân tích số dư) là cách hiệu quả nhất về mặt thuật toán để giải quyết bài toán này.

Lỗi thường gặp

• Làm tròn số hoặc chia số không chính xác khi xử lý số lớn.
• Quên kiểm tra trường hợp cơ sở (base case) của đệ quy.
• Không tối ưu modulo dẫn đến tràn số long long.