chicken mcnugget theorem1 치킨 맥너겟 이론 (chicken mcnugget theorem) https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem 1) 소수 m, n와 임의의 정수 a,b로 나타낼 수 없는 am+bn(소수m,n의 linear combination)의 최대값은 mn-m-n이며 이를 초과하는 수는 모두 am+bn으로 나타낼 수 있다. 또한 am+bn으로 나타낼 수 없는 값의 개수는 다음과 같다 2) 소수가 아닌 일반 양의 정수 m, n에 대해서도 일반화 한다면, 우선 m,n의 linear combination인 am+bn을 다음과 같이 변환한다. 위 두개는 서로소이므로 이들에 대해서 치킨맥너겟 정리를 적용하면 아래와 같이 정리된다. gcd(m,n)을 마저 곱해주면 따라서 lcm(m,n)-m-n을 초과하는 gc.. 2019. 11. 3. 이전 1 다음
