Đếm ước số có số bit 1 nhiều hơn thương khi chia N trong C++

Cho một số nguyên N được coi là ước số, nó sẽ được chia cho các số từ 1 đến N. Nhiệm vụ là đếm số ước số có số bit 1 (set bits) nhiều hơn thương khi chia N cho ước số đó.

Ví dụ

Đầu vào: N = 6

Đầu ra: Số ước số thỏa mãn: 5

Giải thích: Chia N cho 1 đến 6, so sánh số bit 1 của ước số và thương:

• 1 → 6/1=6: bit(1)=1, bit(6)=2 → 1 < 2 (không tính)
• 2 → 6/2=3: bit(2)=1, bit(3)=2 → 1 < 2 (không tính)
• 3 → 6/3=2: bit(3)=2, bit(2)=1 → 2 > 1 (tính)
• 4 → 6/4=1: bit(4)=1, bit(1)=1 → 1 = 1 (tính)
• 5 → 6/5=1: bit(5)=2, bit(1)=1 → 2 > 1 (tính)
• 6 → 6/6=1: bit(6)=2, bit(1)=1 → 2 > 1 (tính)

Kết quả: 5 trường hợp thỏa mãn.

Đầu vào: N = 10

Đầu ra: Số ước số thỏa mãn: 8

Giải thích: Tương tự, kiểm tra từ 1 đến 10, có 8 trường hợp ước số có nhiều bit 1 hơn thương.

Phương pháp sử dụng

• Nhập số nguyên dương N và truyền vào hàm divisors_quotient().
• Hàm divisors_quotient() trả về N - set_quo(N) + 1.
• Hàm set_quo():
  • Khởi tạo start = 1, end = sqrt(N).
  • Vòng lặp WHILE start < end: temp = (start + end) / 2.
  • Nếu verify(temp, N) thì end = temp, ngược lại start = temp + 1.
  • Nếu !verify(start, N) trả về start + 1, ngược lại trả về start.
• Hàm verify(): trả về true nếu val_bit(temp / val) <= val_bit(val).
• Hàm val_bit(): đếm số bit 1 của số nguyên bằng cách chia liên tục cho 2.

Ví dụ mã nguồn

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

int val_bit(int val) { 
    int count = 0; 
    while (val) { 
        val = val / 2; 
        count++; 
    } 
    return count; 
} 

bool verify(int val, int temp) { 
    if (val_bit(temp / val) <= val_bit(val)) { 
        return true; 
    } 
    return false; 
} 

int set_quo(int N) { 
    int start = 1; 
    int end = sqrt(N); 
    while (start < end) { 
        int temp = (start + end) / 2; 
        if (verify(temp, N)) { 
            end = temp; 
        } else { 
            start = temp + 1; 
        } 
    } 
    if (!verify(start, N)) { 
        return start + 1; 
    } else { 
        return start; 
    } 
} 

int divisors_quotient(int N) { 
    return N - set_quo(N) + 1; 
} 

int main() { 
    int N = 10; 
    cout << "Count of divisors having more set bits than quotient on dividing N are: " << divisors_quotient(N); 
    return 0; 
}

Chạy mã trên cho kết quả:

Kết quả

Count of divisors having more set bits than quotient on dividing N are: 8