PKU 3132. Sum of Different Primes
| Time Limit: 5000MS | Memory Limit: 65536K |
| Total Submissions: 2398 | Accepted: 1474 |
설명
어떤 양정수는 한 가지 이상의 서로 다른 소수들의 합으로 나타낼 수 있습니다. 주어진 두 개의 양정수 n 과 k 를 놓고 볼 때, 당신은 n 이라는 양정수를 k 개의 서로 다른 소수들의 합으로 나타내는 방법을 찾아내야 합니다. 다음에 나오는 예시를 보면 확실하겠지만, 같은 소수 집합으로 합의 순서만 바꾸는 것은 같은 방법을 썼다고 간주합니다. 예를 들어 8 은 3 + 5 와 5 + 3 으로 표현 될 수 있지만 이 두 방법은 구별할 수 없기 때문에 하나의 방법입니다.
만약 n 과 k 가 각각 24 와 3 이라면 답은 2가 되는데 그 이유는 {2, 3, 19} 라는 소수집합과 {2, 5, 17} 라는 소수집합, 이 두 집합의 원소들의 합이 24로 같기 때문입니다. 그리고 이 두 집합의 원소들을 제외한 다른 세 개의 소수들의 합으론 24를 만들 수 없습니다. 예를 들어 n = 24 와 k = 2,가 주어졌다면 답은 3개가 되는데 그 이유는 세 개의 집합 {5, 19}, {7, 17} 그리고 {11, 13} 이 있기 때문입니다. 또 n = 2 와 k = 1,이 주어졌다면 답은 1이 되는데 그 이유는 단 하나의 집합{2} 만 이 합이 가능하기 때문입니다. 한편 n = 1 이고 k = 1,이면 답은 0 이 됩니다. 1 은 소수가 아니기 때문에 이런 방식으로 셀 수 없기 때문이지요. 그리고 n = 4 이고 k = 2,라면 그 역시 답이 0이 되는데, 그 이유는 서로 다른 두 개의 소수의 합으로 4를 나타낼 수 없기 때문에 그렇습니다.
주어진 n 과 k 에 대해서 위와 같은 방식으로 답을 찾는 프로그램을 작성하는 것이 당신이 해야 할 일입니다.
입력
입력할 때 데이터셋은 하나의 줄에 두 개의 양정수 n 과 k 를 포함하는데, 이 두 수 사이에는 공백을 두어 입력합니다. 이 때 n ≤ 1120 까지, 그리고 k ≤ 14 까지 가능합니다. 입력을 종료할 때는 두 양정수의 위치에 0 을 각각 넣어서 종료합니다.
출력
입력된 각 데이터셋에 대해서 연관된 한 줄로 출력합니다. 출력할때는 하나의 음이 아닌 정수를 내보내는데, 이 정수는 입력에서 주어진 두 양정수 n 과 k 를 놓고 표현 가능한 방법의 가지수를 나타냅니다. 출력하는 값은 231 보다 작습니다.
입력 예시
24 3 24 2 2 1 1 1 4 2 18 3 17 1 17 3 17 4 100 5 1000 10 1120 14 0 0
출력 예시
2 3 1 0 0 2 1 0 1 55 200102899 2079324314
Source