AllButOne | Topcoder Archive

Problem Statement

We call a sequence A an (N,S)-sequence if it contains N positive integers (numbered 0 through N-1) and the sum of its elements is equal to S.

You're given two ints, S and MOD. You're allowed to pick an arbitrary positive integer N and an arbitrary (N,S)-sequence A. Then, you should compute P = (A[0]*A[1]*...*A[N-1]) modulo MOD.

Compute and return the number of different values of P that can be obtained this way.

Definition

Class:: AllButOne
Method:: countRemainders
Parameters:: int, int
Returns:: int
Method signature:: int countRemainders(int S, int MOD)
(be sure your method is public)

Constraints

S will be between 1 and 500, inclusive.
MOD will be between 2 and 50,000, inclusive.

Examples

```
5
```
```
10
```
```
Returns: 6
```
All values from 1 to 6 (inclusive) are achievable.
```
11
```
```
13
```
```
Returns: 12
```
There's no way to achieve a number divisible by 13.
```
8
```
```
20
```
```
Returns: 14
```
```
500
```
```
5030
```
```
Returns: 5020
```
```
99
```
```
50000
```
```
Returns: 42559
```
```
238
```
```
27184
```
```
Returns: 27168
```
```
499
```
```
499
```
```
Returns: 499
```
```
18
```
```
38467
```
```
Returns: 117
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.