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 를 놓고 표현 가능한 방법의 가지수를 나타냅니다. 출력하는 값은 2³¹ 보다 작습니다.

입력 예시

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

Japan 2006

p.s: 입력 부분 해석이 저만 이상한가요? 일단 문제에 맞게 해석해서 올려봅니다.. Lonewolf dlbo의 조언을 통해 의문을 해결하였습니다.(-)