นับจำนวนตัวหารที่มีบิตเซตมากกว่าผลหารเมื่อหาร N ใน C++

เราได้รับจำนวนเต็ม N ซึ่งถูกพิจารณาว่าเป็นตัวหาร และจะถูกหารด้วยตัวเลขตั้งแต่ 1 ถึง N และภารกิจคือการคำนวณจำนวนตัวหารที่มีจำนวนบิตเซต (set bits) มากกว่าผลหารเมื่อหารด้วย N ที่กำหนด

ตัวอย่าง

Input - int N = 6

Output - จำนวนตัวหารที่มีบิตเซตมากกว่าผลหารเมื่อหาร N คือ: 5

คำอธิบาย - ก่อนอื่น เราจะหาร N ด้วยตัวเลขตั้งแต่ 1 ถึง N และคำนวณบิตเซตของตัวหารและผลหาร เช่น

1 → N = 6 / 1(1) = 6(2) = 1 < 2 = ไม่นับ

2 → N = 6 / 2(1) = 3(2) = 2 = 2 = นับ

3 → N = 6 / 3(2) = 2(1) = 2 > 1 = นับ

4 → N = 6 / 4(1) = 1(1) = 1 = 1 = นับ

5 → N = 6 / 5(2) = 1(1) = 2 > 1 = นับ

6 → N = 6 / 6(2) = 1(1) = 2 > 1 = นับ

ตามที่เห็น เราจะนับกรณีที่ผ่าน และผลลัพธ์คือ 5

Input - int N = 10

Output - จำนวนตัวหารที่มีบิตเซตมากกว่าผลหารเมื่อหาร N คือ: 8

คำอธิบาย - ก่อนอื่น เราจะหาร N ด้วยตัวเลขตั้งแต่ 1 ถึง N และคำนวณบิตเซตของตัวหารและผลหาร เช่น

1 → N = 10 / 1(1) = 10(2) = 1 < 2 = ไม่นับ

2 → N = 10 / 2(1) = 5(2) = 2 = 2 = นับ

3 → N = 10 / 3(2) = 3(2) = 2 = 2 = นับ

4 → N = 10 / 4(1) = 2(1) = 1 < 2 = ไม่นับ

5 → N = 10 / 5(2) = 2(1) = 2 > 2 = นับ

6 → N = 10 / 6(2) = 1(1) = 2 > 1 = นับ

7 → N = 10 / 7(3) = 1(1) = 3 > 1 = นับ

8 → N = 10 / 8(1) = 1(1) = 1 = 1 = นับ

9 → N = 10 / 9(2) = 1(1) = 2 > 2 = นับ

10 → N = 10 / 10(2) = 1(1) = 2 > 1 = นับ

ตามที่เห็น เราจะนับกรณีที่ผ่าน และผลลัพธ์คือ 8

แนวทางที่ใช้ในโปรแกรมด้านล่าง

• รับจำนวนเต็มบวก N และส่งให้ฟังก์ชัน divisors_quotient()
• ภายในฟังก์ชัน divisors_quotient()
  • คืนค่า N - เรียกฟังก์ชัน set_quo(N) + 1 และไปที่ฟังก์ชัน set_quo()
• ภายในฟังก์ชัน set_quo()
  • สร้างตัวแปรชั่วคราว start และ end เริ่มต้น start = 1 และ end = sqrt(N)
  • เริ่มลูป WHILE จนกว่า start < end สร้างตัวแปรชั่วคราว temp = (start + end) / 2
  • ตรวจสอบ IF (เรียกฟังก์ชัน verify() ส่ง temp และ N) แล้วตั้ง end = temp
  • ELSE ตั้ง start = temp + 1
  • IF (!เรียก verify(temp, N)) คืนค่า start + 1
  • ELSE คืนค่า start
• ภายในฟังก์ชัน verify()
  • ตรวจสอบ IF (val_bit(temp/val) < val_bit(val)) คืนค่า true มิฉะนั้น false
• ภายในฟังก์ชัน val_bit()
  • ประกาศตัวแปรชั่วคราว count เก็บผลลัพธ์
  • เริ่มลูป WHILE val มีค่า ภายในลูป ตั้ง val = val / 2 และเพิ่ม count ขึ้น 1
  • คืนค่า count

ตัวอย่าง

#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; 
}

หากเรารันโค้ดข้างต้น จะได้ผลลัพธ์ดังนี้

ผลลัพธ์

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