Kiểm tra số N bắt đầu bằng 1 trong cơ số b C++

Cho số N và cơ số b. Kiểm tra biểu diễn của N trong cơ số b có bắt đầu bằng chữ số 1 không.

Ý tưởng

Số N trong cơ số b có dạng d_m d_{m-1} ... d_0 với d_m ≠ 0.

N bắt đầu bằng 1 ⇔ b^m ≤ N ≤ 2×b^m - 1 với một số m ≥ 0.

Vì m ≤ log₂(N), ta thử mọi m từ 0 đến ⌊log₂(N)⌋.

Chương trình C++

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

bool startsWithOne(long long N, int base) {
    if (N <= 0) return false;
    int maxM = (int)log2(N);
    for (int m = 0; m <= maxM; m++) {
        long long pow = 1;
        for (int i = 0; i < m; i++) pow *= base;
        long long lower = pow;
        long long upper = 2 * pow - 1;
        if (lower <= N && N <= upper) return true;
    }
    return false;
}

int main() {
    long long N; int b;
    cout << "Nhap N va base: "; cin >> N >> b;
    cout << (startsWithOne(N, b) ? "Bat dau bang 1" : "Khong bat dau bang 1") << "\n";
    
    // Test
    cout << "6 base 2: " << (startsWithOne(6,2)?"Yes":"No") << " (110)\n";
    cout << "6 base 4: " << (startsWithOne(6,4)?"Yes":"No") << " (12)\n";
    cout << "19 base 16: " << (startsWithOne(19,16)?"Yes":"No") << " (13)\n";
    return 0;
}

Kết quả

Nhap N va base: 19 16
Bat dau bang 1
6 base 2: Yes (110)
6 base 4: Yes (12)
19 base 16: Yes (13)