EraseToGCD | Topcoder Archive

Problem Statement

You have a sequence S of small positive integers. You want to erase some (possibly none but not all) elements of S in such a way that the greatest common divisor of the resulting sequence becomes exactly goal.

Let W be the number of ways in which the above can be done. Compute and return the value (W modulo (10^9 + 7)).

Definition

Class:: EraseToGCD
Method:: countWays
Parameters:: int[], int
Returns:: int
Method signature:: int countWays(int[] S, int goal)
(be sure your method is public)

Notes

Two ways of erasing are different if the sets of indices of erased elements differ.

Constraints

S will have between 1 and 500 elements, inclusive.
Each element of S will be between 1 and 1000, inclusive.
goal will be between 1 and 1000, inclusive.

Examples

```
{6, 4, 30, 90, 66}
```
```
2
```
```
Returns: 15
```
We must keep the element at index 1 (value 4) because if we don't, all elements that remain will be divisible by 3. In addition to that element we need to keep at least one other element. Any such solution will already have the correct GCD.
```
{8, 8, 8}
```
```
4
```
```
Returns: 0
```
Each possible subsequence has GCD = 8, and 8 is not 4.
```
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
```
```
1
```
```
Returns: 983
```
Almost all of the 1023 possible ways of erasing work.
```
{2, 2, 2, 2, 2}
```
```
2
```
```
Returns: 31
```
All ways of erasing work (and are counted as distinct ways).

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.