Codeforces2 치킨 맥너겟 이론 (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. codeforces #591 div2 C - Save the Nature (이분탐색) 모든 변수를 long long으로 바꿔주니 ac받았다. 배열크기n과 배열을 입력받고, a번째 요소마다 x퍼센트의 기부금을 주는 것에 대한 입력 a,x,b,y를 입력받고, 기부금의 최소금액인 k를 입력받는다. 위와 같이 입력받은 후, k이상의 기부금을 받을 수 있는 최소한의 티켓수를 구하는 문제이다. 문제에서 배열의 순서를 자유롭게 할 수 있다고 한 것에 속아넘어가지 않고, 수학적으로 생각하면 된다. 조건에 맞는 티켓의 최소값을 찾는 이분탐색에 isPossible함수를 O(n)으로 구현해서 전체 O(logn)이다. isPossible함수는 다음과 같이 구현했다. 팔리는 티켓수를 m이라고 할 떄, 1) (x+y)%가 붙는 경우는 t = m/lcm(a,b) 2) x%가 붙는 경우는 r = m/a-t 3) y%.. 2019. 11. 1. 이전 1 다음
