Show problems as
Classic problem #3336HardArrayMathDynamic ProgrammingNumber TheoryEuclidean AlgorithmGreatest Common Divisor

Find the Number of Subsequences With Equal GCD

Real-world version: Matched Gear Benches
Tracked in this browser only
Read Find the Number of Subsequences With Equal GCD on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A machine shop is dividing a crate of spare gears between two benches. gears[i] is the tooth count of the gear at position i.

A split sends every gear to exactly one of three places: bench one, bench two, or back into the crate. Both benches must end up with at least one gear.

A split is matched when the greatest common divisor of the tooth counts at bench one is equal to the greatest common divisor of the tooth counts at bench two.

Two splits are different whenever some position ends up in a different place, so gears that happen to share a tooth count are still told apart by their position, and the two benches are told apart from each other.

Return the number of matched splits. The count can be enormous, so return it modulo 10^9 + 7.

Examples

Example 1

Input
gears = [4, 6, 18, 24]
Output
2

Bench one can take the gear with 6 teeth while bench two takes those with 18 and 24 teeth, leaving the 4-tooth gear in the crate: the divisors are 6 and gcd(18, 24) = 6. Handing those same two rosters to the opposite benches is the other matched split.

Example 2

Input
gears = [3, 3]
Output
2

Each bench takes one of the two gears and both rosters have divisor 3. The two gears sit at different positions, so the two ways of dealing them out are separate splits.

Example 3

Input
gears = [2, 3]
Output
0

Neither bench may be left empty, so one bench gets the 2-tooth gear and the other the 3-tooth gear; the divisors are 2 and 3, which are not equal.

Constraints

  • 1 <= gears.length <= 200
  • 1 <= gears[i] <= 200

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def matched_gear_splits(gears: list[int]) -> int:
Java
public int matchedGearSplits(int[] gears)

More on the same topics