在 Python 中查詢正數 M，使得 gcd(N^M, N&M) 最大

假設我們有一個數字 N，我們必須找到一個正數 M，使得 gcd(N^M, N&M) 儘可能大，並且 m < n。我們還將返回獲得的最大 gcd。

因此，如果輸入是 20，則輸出將是 31

為了解決這個問題，我們將遵循以下步驟：

如果 bit_count(n) 等於 0，則
- 對於 i 從 2 到 int(n 的平方根) + 1，執行以下操作：
  - 如果 n mod i 等於 0，則
    - 返回 int(n / i)
否則，
- val := 0
- p :=
- dupn := n
- 當 n 不為零時，執行以下操作：
  - 如果 (n AND 1) 等於 0，則
    - val := val + p
  - p := p * 2
  - n := n >> 1
- 返回 gcd(val XOR dupn, val AND dupn)
返回 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))

輸入

輸出

Arnab Chakraborty

更新於：2020年8月28日

81 次檢視

開啟您的職業生涯

完成課程獲得認證

開始學習