nodeal dev story

주어진 범위의 수들 중 k개의 등차수열의 합으로 표현가능한 수의 수를 구하는 문제다. 초항과 공차가 반드시 자연수이므로 각 k에 맞는 최소한의 수가 존재한다. k = 2) 1 + 2 = 3이므로, left가 3보다 작더라도 3부터 시작한다. 초항 n, 공차 d에서 n + n + d = 2n + d를 만족하는 모든 수가 해당된다. 따라서 3이상의 모든 수가 길이가 2인 등차수열의 합이다. (예: 4 = 1 + 3, 5 = 1 + 4 ...) k = 3) 1 + 2 + 3 = 6이므로, left가 6보다 작더라도 6부터 시작한다. 초항 n, 공차 d에서 n + n + d + n + 2d = 3n + 3d를 만족하는 모든 수가 해당된다. 따라서 6이상의 모든 3의 배수가 길이가 3인 등차수열의 합이다. k =..

이게 왜 solved.ac 골드 1에 있는 문제인지 의문스럽다. 문제의 제한 시간은 2초, 1,000,000보다 작거나 같은 모든 L에 대해 선분의 길이 쌍을 모두 구하고도 남을 시간이다. (3, 4), (5, 12), (8, 15) ... 와 같은 쌍을 모두 준비하는 방법을 생각해보자. 첫번째 조건은 세 성분을 잘 조합했을 때 '피타고리안 트리플'이 되어야 한다는 것이다. 3, 4가 있다면 다른 한 수는 5가 되어야 한다는 것이다. 두번째 조건은 폭보다 높이가 커야한다는 것으로, (3, 4), (4, 3)에서는 (3, 4)만이 유효하다는 것을 알 수 있다. 마지막 조건은 두 수의 최대공약수가 1이어야 한다는 것, 다시 말해 두 수가 서로소여야 한다는 것이다. (3, 4)는 허용해도, (6, 8)은 안 ..