Python - Tìm số dương M sao cho gcd(N^M, N&M) lớn nhất

Giả sử chúng ta có một số N, chúng ta phải tìm một số dương M sao cho gcd(N^M, N&M) càng lớn càng tốt và M < N. Chúng ta cũng trả về giá trị gcd lớn nhất đó.

Ví dụ, nếu N=20, đầu ra là 31.

Giải pháp:

• Nếu bit_count(n) == 0 (tức là n là lũy thừa của 2): tìm ước số nhỏ nhất >1 của n, trả về n/i.
• Ngược lại: val=0, p=1, dupn=n; while n: nếu (n&1)==0: val+=p; p*=2; n>>=1; return gcd(val^dupn, val&dupn)
• Trả về 1

Ví dụ

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))

Đầu vào

20

Đầu ra

31