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에 대해
  - n mod i가 0과 같으면
    - int(n / i)를 반환
그렇지 않으면
- 값:=0
- p :=
- dupn :=n
- n이 0이 아닌 동안 do
  - (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))