找到一个正数M，使gcd（N ^ M，N＆M）在Python中最大

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个数字N，我们必须找到一个正数M，以使gcd（N ^ M，N＆M）尽可能大并且m <n。我们还将返回由此获得的最大gcd。

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

为了解决这个问题，我们将遵循以下步骤-

  • 如果bit_count(n)与0相同，则

    • 如果n mod i等于0，则

    • 返回int（n / i）

    • 对于范围2到int（(n)的平方根）+1的i，执行

    • 除此以外，

      • 如果（n AND 1）等于0，则

      • p：= p * 2

      • n：= n >> 1

      • 值：=值+ p

      • 值：= 0

      • p：=

      • 杜邦：= n

      • 当n不为零时，

      • 返回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

      以上是 找到一个正数M，使gcd（N ^ M，N＆M）在Python中最大 的全部内容， 来源链接： utcz.com/z/326814.html

      回到顶部