หาจำนวนเต็มบวก M ที่ทำให้ gcd(N^M, N&M) สูงสุดใน Python

สมมติว่าเรามีตัวเลข N เราต้องหาจำนวนเต็มบวก M ที่ทำให้ gcd(N^M, N&M) ใหญ่ที่สุด และ m < n จะคืนค่า gcd ที่มากที่สุดที่ได้ด้วย

ตัวอย่าง

หากอินพุตคือ 20 ผลลัพธ์จะเป็น 31

ขั้นตอนการแก้ปัญหา

1. ถ้า bit_count(n) == 0:
   • ลูป i จาก 2 ถึง int(sqrt(n)) + 1:
     • ถ้า n % i == 0 ให้คืนค่า int(n / i)
2. อื่นๆ:
   • val := 0, p := 1, dupn := n
   • ในขณะที่ n ไม่เป็นศูนย์:
     • ถ้า (n & 1) == 0 ให้ val := val + p
     • p := p * 2
     • n := n >> 1
   • คืนค่า gcd(val ^ dupn, val & dupn)
3. คืนค่า 1

การใช้งาน

from math import gcd, sqrt

def bit_count(n):
    if n == 0:
        return 0
    else:
        return ((n & 1) == 0) + bit_count(n >> 1)

def maximum_gcd(n):
    if bit_count(n) == 0:
        for i in range(2, int(sqrt(n)) + 1):
            if n % i == 0:
                return int(n / i)
    else:
        val = 0
        p = 1
        dupn = n
        while n:
            if (n & 1) == 0:
                val += p
            p = p * 2
            n = n >> 1
        return gcd(val ^ dupn, val & dupn)
    return 1

n = 20
print(maximum_gcd(n))

อินพุต

20

เอาต์พุต

31