Hiểu bài toán

Cho một số nguyên dương N (1 ≤ N ≤ 10^18). Một số X được gọi là 'số đẹp' nếu X = 2^n hoặc X = 3 * 2^n (với n là số nguyên không âm). Bài toán yêu cầu tìm số đẹp lớn nhất không vượt quá N (gọi là X), từ đó tính số lượng bài tập cần bỏ đi tối thiểu là N - X.

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

Cách Brute Force (Duyệt qua tất cả)

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

int main() {
    long long N;
    cin >> N;

    long long min_remove = N; // Khởi tạo lớn nhất (bỏ hết)

    for (int n = 0; n <= 60; ++n) {
        long long power2 = 1LL << n;
        if (power2 <= N) {
            min_remove = min(min_remove, N - power2);
        }

        if (3LL * power2 <= N) {
            min_remove = min(min_remove, N - 3LL * power2);
        }
    }

    cout << min_remove << endl;
    return 0;
}

• Time Complexity: O(log N)
• Space Complexity: O(1)

Cách tiếp cận này sinh ra tất cả các số đẹp có thể nhỏ hơn hoặc bằng N và tìm số đẹp lớn nhất.

1. Biến min_remove được khởi tạo bằng N (trường hợp xấu nhất là phải bỏ hết).
2. Vòng lặp chạy từ n = 0 đến 60. Với N lên tới 10^18, 2^60 (khoảng 1.15e18) là đủ lớn để bao quát hết các trường hợp.
3. Trong mỗi bước lặp, tính power2 = 2^n.
4. Nếu power2 <= N, cập nhật kết quả: min_remove = min(min_remove, N - power2).
5. Nếu 3 * power2 <= N, cập nhật kết quả: min_remove = min(min_remove, N - 3 * power2).
6. Kết quả cuối cùng chính là số lượng bài cần bỏ.

Cách Tối ưu hóa Logic (Tìm số đẹp lớn nhất)

#include <stdio.h>

int main(){
    long long n;
    scanf("%lld",&n);
    long long a = 1, b = 1, tmp = 1;
    for(int i = 0;i<64;i++){
        if(a>n){
            a /= 2;
            break;
        }
        else if(a == n){
            break;
        }
        a *= 2;
    }
    for(int i = 0;i<64;i++){
        if(b>n){
            tmp /= 4;
            b = 3*tmp;
            break;
        }
        else if(b == n){
            break;
        }
        b = 3*tmp;
        tmp *= 2;
    }
    long long res = (n-a)<(n-b)?(n-a):(n-b);
    printf("%lld",res);
    return 0;
}

• Time Complexity: O(log N)
• Space Complexity: O(1)

Cách tiếp cận này ch problème thành hai bài toán con: tìm số đẹp thuộc dạng 2^n lớn nhất ≤ N và tìm số đẹp thuộc dạng 3*2^n lớn nhất ≤ N.

1. Duyệt a (dạng 2^n): Tăng a lên gấp đôi cho đến khi a vượt quá N, sau đó lùi lại một bước (chia 2) để có số đẹp lớn nhất.
2. Duyệt b (dạng 3*2^n): Tăng b lên gấp đôi (nhân 3 với 2^n) cho đến khi vượt quá N, sau đó lùi lại một bước.
3. So sánh hai số đẹp tìm được, số nào gần N hơn (chênh lệch nhỏ hơn) thì chọn. Cách này cũng hiệu quả tương đương cách 1 nhưng logic hơi rắc rối hơn một chút.

Cách Sử dụng 128-bit Integer

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

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

    unsigned long long N;
    if (!(cin >> N)) return 0;

    unsigned long long best = 0;
    __int128 p = 1; // p = 2^k, dùng __int128 để tính 3*p an toàn

    while (p <= (__int128)N) {
        // 2^k
        if ((unsigned long long)p <= N) best = max(best, (unsigned long long)p);
        // 3 * 2^k
        __int128 threep = p * 3;
        if (threep <= (__int128)N) best = max(best, (unsigned long long)threep);
        p *= 2;
    }

    cout << (N - best) << '\n';
    return 0;
}

• Time Complexity: O(log N)
• Space Complexity: O(1)

Cách tiếp cận này sử dụng kiểu dữ liệu __int128 (có sẵn trong GCC/Clang) để tránh tràn số khi nhân 3.

1. Biến p (dạng __int128) bắt đầu bằng 1.
2. Trong vòng lặp while, p được nhân đôi liên tục.
3. Kiểm tra p (dạng 2^n) và p * 3 (dạng 3*2^n) có ≤ N hay không. Nếu có thì cập nhật best.
4. Vì __int128 có thể lưu số lớn hơn unsigned long long, phép nhân p * 3 sẽ an toàn ngay cả khi p lớn. Cách này cũng O(log N) và rất an toàn về số học.

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

Bài học kinh nghiệm

• Bài toán chỉ yêu cầu tìm số đẹp lớn nhất không vượt quá N, không cần tìm số đẹp nhỏ nhất.
• Số đẹp có hai dạng duy nhất: 2^n và 3*2^n.
• Với N ≤ 10^18, số mũ n tối đa chỉ khoảng 60 (vì 2^60 ≈ 1.15×10^18), nên độ phức tạp O(log N) là hoàn hảo.

Lỗi thường gặp

• Tràn số nguyên (Integer Overflow): Khi tính 3 * 2^n nếu n lớn (ví dụ n=60), giá trị sẽ vượt quá 2^63-1 của kiểu long long (khoảng 9.2e18). 3 * 2^60 ≈ 3.45e18, vẫn an toàn trong long long (signed), nhưng nếu dùng unsigned long long thì 2^60 là 1.15e18, nhân 3 là 3.45e18, vẫn an toàn (max ~1.8e19). Tuy nhiên, nếu tính 2^62 hoặc 2^63 thì sẽ tràn. Vòng lặp không được chạy quá giới hạn an toàn của kiểu số.
• Xử lý số lớn: N có thể lên tới 10^18, cần dùng long long (hoặc unsigned long long) trong C++/C.
• Trường hợp N rất nhỏ: Cần đảm bảo vòng lặp hoặc logic hoạt động chính xác với N = 1.