어려운 정수론 문제 2개
문제1: 소수 \(p\)와 양의 정수 \(a_1, a_2, ... , a_p\)에 대하여 다음 조건을 만족하는 양의 정수 \(k\)가 존재함을 보여라. $$ a_1+k, a_2+2k, ... , a_p+pk $$ 를 \(p\)로 나눈 나머지들이 적어도 \(p/2\)개 이상의 서로 다른 값를 갖는다. [2018 USAMO P4] (sol) 더보기 \(k=1, 2, ... , p\)에 대해 무향그래프 \(G=G_1, G_2, ... , G_p\) 를 구성하자. \(a_i\)에 해당하는 점을 \(i\)로 둔다. \(a_i+ik\equiv a_j+jk \quad(\textup{mod} \; p) \)를 만족하면 점 \(i\)와 \(j\)를 잇는다. (단, \(i < j\)) 이 때, $$ a_i+ik\equiv..
2023. 12. 26.
백준 1234 / C++
https://www.acmicpc.net/problem/1234 1234번: 크리스마스 트리 첫째 줄에 트리의 크기 N, 빨강의 개수, 초록의 개수, 파랑의 개수가 주어진다. N은 10보다 작거나 같다. 빨강, 초록, 파랑의 개수는 0보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net [ 풀이 ] dp[h][r][g][b]를 h높이를 채울 것이고 지금까지 r, g,b만큼 색상을 쓴 경우의 수라고 하자. 상태전이는 다음과 같다. 1. 한 색으로 h칸을 모두 칠한다. : dp[h+1][r+h][g][b] 로 전이 (g, b도 마찬가지) 2. h가 짝수면 두개를 골라 절반씩 칠한다. : dp[h+1][r+h/2][g+h/2][b] * h!/(h/2)!(h/2)! 로 전이 (g, b도 마..
2022. 8. 8.