Tìm một số dương M sao cho gcd (N ^ M, N &M) là cực đại trong Python

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) lớn nhất có thể và m

Vì vậy, nếu đầu vào là 20, thì đầu ra sẽ là 31

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu bit_count (n) giống 0, thì
  • đối với tôi trong phạm vi 2 đến int (căn bậc hai của (n)) + 1, thực hiện
    • nếu n mod i giống 0, thì
      • return int (n / i)
• nếu không,
  • val:=0
  • p:=
  • Dupn:=n
  • trong khi n khác 0, hãy thực hiện
    • nếu (n VÀ 1) giống 0, thì
      • val:=val + p
    • p:=p * 2
    • n:=n>> 1
  • trả về gcd (val XOR lặp lại, val VÀ lặp lại)
• trả lại 1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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