문제 링크 (2024/9/10 기준) Gold V 문제 읽기 $1$부터 $N$까지의 자연수를 색칠해야 합니다. 단, 서로소인 두 자연수는 서로 다른 색으로 칠해야 하고, 최소한의 색을 사용해야 합니다. 예시 $n=5$일 때, $1\ 2\ 3\ 4\ 5$를 $\color{salmon}1\ \color{sandybrown}2\ \color{seagreen}3\ \color{sandybrown}4\ \color{skyblue}5$로 $4$가지 색을 이용하여 색칠할 수 있습니다. 따라서, 정답은 $1\ 2\ 3\ 2\ 4$입니다. (색의 순서는 상관이 없습니다. 최소 개수를 만족하기만 한다면 정답으로 인정됩니다. 또한, $6$을 $2$와 같은 색으로 칠하든 $3$과 같은 색으로 칠하든 모두 정답으로 인정됩니다....
문제 링크 (2024/7/17 기준) Diamond V 문제 읽기 연속된 정수 구간 $Q$와 연속된 양의 정수 구간 $P$가 있습니다. 연속된 구간 $PQ$에 대하여, 구간 $Q$의 길이 $q$가 주어졌을 때, 구간 $P$의 합과 구간 $Q$의 합이 같을 때의 가능한 $p$가 몇 개나 있을지 세어봅시다. 예시 $\underbrace{9+10+11+12} _{P} = \underbrace{13+14+15} _{Q}$는 $p=4$, $q=3$인 예시입니다. $\underbrace{4+5+6+7+8} _{P} = \underbrace{9+10+11} _{Q}$은 $p=5$, $q=3$인 예시입니다. 풀이 먼저, $p>q$임을 캐치합시다. 구간 $P$는 항상 구간 $Q$의 왼쪽에 붙어있기 때문에, $p\leq q$라면, 항상 구간 $P$의 합은 구간 $Q$의 합보다 작습니다....
Intro 등비수열 $a_{n} = ar^{n-1}$의 합은 $$ S_n = \begin{cases} an &\text{if } r=1\ \newline \frac{a(r^n - 1)}{r-1} &\text{otherwise} \end{cases} $$ 로 나타낼 수 있습니다. $r=1$일 때 $S_n$이 다른 이유는, $\frac{a(r^n - 1)}{r-1}$의 분모가 $0$이 되기 때문입니다. 이때는, $1$항부터 $n$항까지가 모두 $a$로 같으니, 간단하게 $an$으로 나타낼 수 있습니다. $n$이 커지면 커질 수록 $S_n$은 (말 그대로) 기하급수적으로 커지기 때문에, 일반적으로 PS에서는 $S_n$을 $m$으로 나눈 나머지를 구하도록 합니다. 따라서, 이 글에서는 등비수열의 합 $S_n\ \textrm{mod}\ m$을 빠르게 구할 방법을 소개하겠습니다....