Pythonでgcd（N ^ M、N＆M）が最大になるような正の数Mを見つけます

数Nがあるとすると、gcd（N ^ M、N＆M）が可能な限り大きく、m

したがって、入力が20のような場合、出力は31になります

これを解決するには、次の手順に従います-

• bit_count（n）が0と同じ場合、
  • 範囲2からint（（n）の平方根）+ 1のiの場合、do
    • n mod iが0と同じ場合、
      • return int（n / i）
• それ以外の場合、
  • val：=0
  • p：=
  • dupn：=n
  • nがゼロ以外の場合は、
    • （n AND 1）が0と同じ場合、
      • val：=val + p
    • p：=p * 2
    • n：=n>> 1
  • return 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