숫자 N이 주어졌을 때, gcd(N^M, N&M)의 값이 최대가 되도록 하면서 조건 M < N을 만족하는 양수 M을 찾는 것이 이번 문제의 목표입니다. 마지막에는 구할 수 있는 최대 gcd 값도 함께 반환해야 합니다.
예를 들어 입력값이 20이라면 결과는 31이 됩니다.
해결 전략
이 문제의 핵심은 비트 연산의 성질을 활용하는 것입니다. XOR과 AND의 최대공약수(gcd)를 극대화하기 위해 다음 두 가지 경우로 나누어 접근합니다.
1. N의 이진수 표현에 0인 비트가 존재하는 경우
N을 이진수로 나타냈을 때 0인 자리를 모두 1로 뒤집은 값을 M으로 선택합니다. 즉, M은 N의 비트 길이(k) 안에서 N의 보수(complement)입니다. 이렇게 선택하면 다음과 같은 성질이 성립합니다.
- N ^ M = 2^k − 1 : 모든 비트가 1인 수가 됩니다.
- N & M = 0 : 겹치는 비트가 없습니다.
따라서 gcd(N^M, N&M) = gcd(2^k − 1, 0) = 2^k − 1이 되며, 이보다 큰 값은 존재할 수 없으므로 이것이 최적해입니다. 또한 M의 최상위 비트는 항상 0이므로 M < N 조건도 자연스럽게 만족됩니다.
2. N의 모든 비트가 1인 경우 (N = 2^k − 1 꼴)
이 경우에는 어떤 M을 선택하더라도 N & M이 N보다 작아질 수밖에 없어 gcd가 N에 가까워지기 어렵습니다. 따라서 2부터 √N까지 탐색하며 가장 작은 약수 i를 찾고, N / i(자기 자신을 제외한 가장 큰 약수)를 반환하는 것이 최선입니다. 만약 N이 소수라면 1을 반환하게 됩니다.
구현 코드
다음은 위 전략을 Python으로 구현한 예제입니다.
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))코드 설명
bit_count()함수는 재귀 호출을 통해 n의 이진 표현에서 0인 비트의 개수를 세어 반환합니다.maximum_gcd()함수는 0인 비트가 없으면(모든 비트가 1이면) 약수 탐색으로 최대 약수를 찾고, 그렇지 않으면 while 루프를 돌며 n의 0인 비트 자리를 1로 채운 보수 값val을 만듭니다.- 마지막으로
gcd(val ^ dupn, val & dupn)을 계산하여 최대 gcd를 반환합니다.
실행 결과 확인
입력
20
출력
31
n = 20은 이진수로 10100이고, 여기서 0인 비트를 뒤집은 M = 01011(십진수 11)을 적용하면 N ^ M = 11111(십진수 31), N & M = 0이 되어 gcd는 31이 됩니다. 이것이 가능한 최댓값임을 알 수 있습니다.