숫자 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)를 반환
- n mod i가 0과 같으면
- 2 ~ int((n)의 제곱근) + 1 범위의 i에 대해
- 그렇지 않으면
- 값:=0
- p :=
- dupn :=n
- n이 0이 아닌 동안 do
- (n AND 1)이 0과 같으면
- val :=val + p
- p :=p * 2
- n :=n>> 1
- (n AND 1)이 0과 같으면
- 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