|
|
SPOJ Problem Set (classical)
1391. Summing to a Square Prime
Problem code: CZ_PROB1
|
SP2 = {p | p = x12 + x22 for some x1, x2 belonging to Z} is the set of all primes that can be represented as the sum of any two squares. The function SP2(n) gives the nth prime number from the set SP2. Now, given two integers n (0P2(n), k) where p(a, b) gives the number of unordered ways to sum to the given total ‘a’ with ‘b’ as its largest part.
For example: p(5, 2) = 3 {2+2+1, 2+1+1+1, and 1+1+1+1+1}. Here 5 is the total with 2 as the largest part.
Input
The first line gives the number of test cases T followed by T lines of integer pairs, n and k.
Scope:
0 < T < 501
0 < n < 501
1 < SP2(n) < 7994
0 < k < 4
Output
The p(SP2(n), k) for each n and k. Append a newline character to every test cases’ answer.
Example
Input:
3
2 2
3 2
5 3
Output:
3
7
85
| Added by: | Rahul |
| Date: | 2007-03-10 |
| Time limit: | 2s
|
| Source limit: | 3000B |
| Languages: | All except: ERL TECS JS |
| Resource: | Sam Collins |
|
|
|
|
RSS