在 Python 中查找一个正数 M，使得 gcd(N^M,N&M) 最大

假设我们有一个数 N，我们必须查找一个正数 M，使得 gcd(N^M, N&M) 尽可能大，并且 m < n。我们还将返回由此获得的最大 gcd。

因此，如果输入为 20，则输出为 31

要解决这个问题，我们将遵循以下步骤 −

• 如果 bit_count(n) 与 0 相同，则
  • 对于范围为 2 到 int((n) 的平方根) + 1 的 i，执行
    • 如果 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))
  

  输入

  20
  

  输出

  31
  

  ---

  相关文章

  • 在 Python 中查找给定双调序列中的双调点
  • 在 Python 中查找需要 k 次合并排序调用的数组
  • 在 Python 中查找一个元素，该元素将数组分成两个乘积相等的子数组
  • 在 Python 中查找数组中元素，使得元素形成严格递减和递增序列
  • 在 Python 中查找由字符映射到数字的数字所形成的所有字符串
  • 查找给定字符串的所有回文子字符串 - Python 中的集合 2
  • 在 Python 中查找给定数组中的所有好索引\
  • 在 Python 中查找给定字符串的所有不同回文子字符串
  • 在 Python 中查找一个字符串，使得每个字符的字典顺序都大于其紧邻的下一个字符
  • 在 Python 中以线性时间找到大小为 3 的排序子序列\

  ---

  打印 下一节 ❯❮ 上一节