문제 링크
(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$의 합보다 작습니다. 따라서, $p>q$여야만 두 구간의 합이 같을 수 있습니다.

양의 정수 $n$이 구간 $P$의 오른쪽 끝이라고 합시다.
구간 $Q$의 합은 당연히 양의 정수이므로, 구간 $P$의 합이 양의 정수가 되기 위해서는, $n$이 양의 정수여야 함이 자명합니다.

구간 $P$의 합은, $\underbrace{n+(n-1)+\cdots+(n-p+1)} _{p\text{ terms}}$이므로, $pn-\frac{p(p-1)}{2}$로 정리할 수 있습니다.
같은 방법으로, 구간 $Q$의 합은, $\underbrace{(n+1)+(n+2)+\cdots+(n+q)} _{q\text{ terms}}$이므로, $qn+\frac{q(q+1)}{2}$로 정리할 수 있습니다.

두 합이 같아야 하므로, $pn-\frac{p(p-1)}{2}=qn+\frac{q(q+1)}{2}$로 놓고, 식을 조금 변형합시다.
$(p-q)n=\frac{p^2 + q^2}{2} - \frac{p-q}{2}$, $p>q$이므로, 양변을 $(p-q)$로 나누면, $n=\frac{p^2 + q^2}{2(p-q)}-\frac 1 2$입니다.
$p^2 + q^2 = p^2 - q^2 + 2q^2 = (p+q)(p-q) + 2q^2$를 이용해서 다시 정리해주면,
$n=\frac{p+q-1}{2} + \frac{q^2}{p-q}$가 됩니다.
이를 만족하는 모든 $n$, $p$의 쌍을 찾아봅시다!

$n$이 양의 정수이므로, $p$, $q$의 홀짝성(parity)에 따라 케이스를 나눠야 합니다.

1-1. $p$는 홀수, $q$는 짝수

$p+q$와 $p-q$는 모두 홀수입니다.
$\frac{p+q-1}{2}$은 양의 정수이고, $\frac{q^2}{p-q}$도 양의 정수여야 합니다.

따라서, $(p-q) \vert q^2$입니다.

1-2. $p$는 홀수, $q$는 홀수

$p-q$와 $p+q$가 모두 짝수입니다.
$\frac{p+q-1}{2}$이 정수가 아니므로, $\frac{q^2}{p-q}$가 $\frac{2m-1}{2}$꼴이어야 합니다. (단, $m$은 양의 정수)

따라서, $\frac{q^2}{p-q} = \frac{2q^2}{2(p-q)} = \frac{1}{2} \times \frac{2q^2}{p-q}$로 변형할 수 있고, $(p-q) \vert 2q^2$입니다.

2-1. $p$는 짝수, $q$는 홀수

$p-q$와 $p+q$가 모두 홀수입니다.
$\frac{q^2}{p-q}$이 정수여야 하므로, $(p-q) \vert q^2$.

약간의 관찰을 더 해봅시다.
$p-q$가 홀수이므로, $q^2$의 $2$ 소인수들은 있으나 마나입니다. ($q$가 짝수이므로 반드시 $2$를 적어도 하나 소인수로 갖는데, $p-q$는 홀수이므로 $2$를 소인수로 가질 수 없습니다.)
$q=2^k \times r$이라고 하면, $(p-q) \vert r^2$입니다.

2-2. $p$는 짝수, $q$는 짝수

$p-q$와 $p+q$가 모두 짝수입니다.
$\frac{p+q-1}{2}$이 정수가 아니므로, $\frac{q^2}{p-q}$가 $\frac{2m-1}{2}$꼴이어야 합니다. (단, $m$은 양의 정수)

2-1. 에서 사용한 아이디어를 가져와서, $q^2 = 2^{2k} \times r^2$이고, $p-q$는 $2^{2k+1} \times s$꼴이어야 합니다. (단, $s$는 홀수)

다시 정리해보면, $\frac{q^2}{p-q} = \frac 1 2 \times \frac{r^2}{s}$이므로, $s \vert r^2$입니다.

결론

위의 4가지 케이스를 정리해 봅시다.

1-1. 1-2. 케이스를 정리해 보면, 1-1.에서 가능한 $p$의 개수는 $q$와 $q^2$가 모두 홀수이므로, $q^2$의 약수의 개수와 같다는 것을 알 수 있고, 1-2.에서 가능한 모든 $p-q$들은 1-1.에서 가능한 모든 $p-q$들에 $2$를 곱한 값이고, 이들은 서로 홀짝성이 다르기 때문에, 전부 서로 다른 정수임을 알 수 있습니다.

따라서, $q$가 홀수일 때 가능한 $p$의 개수는 $q^2$의 약수의 개수의 $2$배가 됩니다.

2-1. 2-2. 케이스도 정리해 보면, 2-1.에서의 $p-q$가 가질 수 있는 값이 $r^2$의 약수뿐이고, 2-2.에서 $s$가 가질 수 있는 값도 $r^2$의 약수뿐이니, 가능한 $p-q$와 $s$의 개수는 각각 $r^2$의 약수의 개수로 같습니다. 다만, 2-2.의 $p-q$는$s \times 2^{2k+1}$이므로 2-1.에서의 $p-q$와 각각 다르고, 홀짝성도 다르므로, 전부 서로 다른 정수임을 알 수 있습니다.

따라서, $q$가 짝수일 때 가능한 $p$의 개수는 $q=2^k \times r$인 홀수 $r$에 대하여, $r^2$의 약수의 개수의 $2$배가 됩니다.

1-1.~2-2.를 모두 일반화 시킬 수도 있습니다. $q$가 $2$로 나누어떨어지지 않을 때까지 나눈 수를 $q^{\prime}$이라고 하면, $\lbrace q^{\prime} \rbrace ^ 2$의 약수의 개수의 $2$배가 문제의 정답이 됩니다.

구현은 에라토스테네스의 체를 쓰든 폴라드-로를 쓰든 넉넉하게 통과됩니다.
참고로 저는 안전하게 폴라드-로를 사용했습니다.

약수의 개수를 구하는 방법은… 중학교 수학 내용이니, 다들 아시길 바라며 넘어가겠습니다.

후기

제가 처음으로 자력솔에 성공한 다이아몬드 문제입니다. 난이도 외에 어떠한 정보도 없이 스스로 해결한 문제라 더욱 뿌듯하네요.
3일정도 시간이 걸렸고 (사실 요즘 ps를 잘 안 하긴 합니다.), 공책도 6장 넘게 사용했습니다.

블로그에 올린 이유는 문제가 되게 재밌었기도 하고, 백준 메모에 $\TeX$ 문법으로 남겨둔 수식도 많았고, 이미 다른 분이 블로그에 먼저 올리셨는데, 저와 접근이 조금 달라 보여서 올려봤습니다.

읽어주셔서 감사합니다.