EraseToGCD
TCO19 SRM 748 · 2019-01-09 · by misof
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)).
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.
{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).
{6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,15,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,10,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6}
1
Returns: 847620756
Submissions are judged against all 58 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EraseToGCD with a public method int countWays(vector<int> S, int goal) · 58 test cases · 2 s / 256 MB per case