[BOJ 1419] 등차수열의 합

문제 링크 : https://www.acmicpc.net/problem/1419

본문

첫 항이 x이고 공차가 d인 등차수열의 첫 k개의 항은 x, x+d, x+2d, ..., x+(k-1)d이다. x와 d가 자연수인 등차수열의 첫 k개의 항의 합으로 나타낼 수 있는 수 중에서, l 이상이고 r 이하인 수가 몇 개인지 구하는 프로그램을 작성하시오.

입력

자연수 l, r, k가 순서대로 한 줄에 하나씩 주어진다. (1 ≤ l ≤ r ≤ 1,000,000,000, 2 ≤ k ≤ 5)

출력

첫째 줄에 조건을 만족하는 수의 개수를 출력한다.

제한

시간 제한	메모리 제한
2sec	128MB

---

풀이

$l \leq i \leq r$인 모든 $i$에 대해 $i$가 존재할 수 있도록 하는 자연수 $x$와 $d$가 있는지 확인해야하는 문제이다. 첫 항이 $x$이고 공차가 $d$인 등차수열의 일반항은 $x + id$이다. 이 때 등차수열의 첫 $k$개의 항의 합은 $S_k = (x + d) + \cdots + (x + (k-1)d) = kx + d \sum_{i=1}^{k-1} i$가 된다. 어떻게 제한 시간 내에 넓은 부분에 대해 계산해낼 수 있을까?

다행히도 $k$의 범위가 매우 적다. $2 \leq k \leq 5$이므로, $k$의 값에 따라 우선 모든 경우를 찾아보자. 입력으로 주어진다고는 하지만, 어짜피 4가지 경우를 모두 계산해낼 줄 알아야한다.

• $k = 2$인 경우 :: $S_{k=2} = 2x + d$
  • $S_{k=2}$의 최솟값은 $3$이다
  • case work를 통해 $i \geq 3$인 모든 수를 만들 수 있다는 것을 알 수 있다
• $k = 3$인 경우 :: $S_{k=3} = 3x + 3d$
  • $S_{k=3}$의 최솟값은 $6$이다
  • 마찬가지의 방법으로, $i \geq 6$인 모든 3의 배수를 만들 수 있다는 것을 알 수 있다
• $k = 4$인 경우 :: $S_{k=4} = 4x + 6d$
  • $S_{k=4}$의 최솟값은 $10$이다
  • 다른 경우에 비해 조금 까다롭다. $i=10$과 $i \geq 14$인 모든 2의 배수를 만들 수 있다는 것을 알 수 있다
• $k = 5$인 경우 :: $S_{k=5} = 5x + 10d$
  • $S_{k=5}$의 최솟값은 $15$이다
  • 마찬가지의 방법으로, $i \geq 15$인 모든 5의 배수를 만들 수 있다는 것을 알 수 있다

의외로 해보면 간단한 규칙이 있는 수학 문제임을 알 수 있다. 각 수를 제대로 셀 수 있는 코드를 구현하는 것이 목적.

소스코드

Github Link : Source Code

참고 알고리즘 :