치킨 맥너겟 이론 (chicken mcnugget theorem)

알고리즘/메모

sun__ 2019. 11. 3. 18:39

소수 m, n와 임의의 정수 a,b로 나타낼 수 없는 am+bn(소수m,n의 linear combination)의 최대값은 mn-m-n이며 이를 초과하는 수는 모두 am+bn으로 나타낼 수 있다.

또한 am+bn으로 나타낼 수 없는 값의 개수는 다음과 같다

소수가 아닌 일반 양의 정수 m, n에 대해서도 일반화 한다면,

우선 m,n의 linear combination인 am+bn을 다음과 같이 변환한다.

위 두개는 서로소이므로 이들에 대해서 치킨맥너겟 정리를 적용하면 아래와 같이 정리된다.

gcd(m,n)을 마저 곱해주면

따라서 lcm(m,n)-m-n을 초과하는 gcd(m,n)의 배수는 am+bn꼴로 나타낼 수 있다.