Overview

For each card \(i\), construct “front prime factorization exponent vector − back prime factorization exponent vector”. Then use Meet-in-the-Middle to determine whether there exists a chosen set \(S\) whose total sum of these vectors is \(0\) (which means the products are equal), and find the minimum value of \(|S|\).

Observations

Key Insight: Equality of products can be checked via “sums of prime exponent vectors”

The condition [ \prod_{i\in S} Pi=\prod{i\in S} Q_i ] can be verified by prime factorizing both sides and comparing the exponents for each prime.

For example, for primes \(2,3,5,\dots\), define the prime exponent vector of a number \(x\) as [ \mathrm{vec}(x)=(e_2,e_3,e_5,\dots) ] Then we have [ \mathrm{vec}\Big(\prod x\Big)=\sum \mathrm{vec}(x) ] (exponents add up under multiplication).

Therefore, for each card, define [ D_i=\mathrm{vec}(P_i)-\mathrm{vec}(Qi) ] and the condition becomes equivalent to [ \sum{i\in S} D_i=\mathbf{0} ]

Why naively trying all subsets is difficult

• There are \(2^N\) candidate subsets for \(S\) (up to \(2^{22}\approx 4.2\times 10^6\)).
• Moreover, handling products directly leads to enormous numbers, causing overflow and computational cost issues (even in Python, large integers are slow).
• Finding the “minimum \(|S|\)” requires managing subset sizes while performing exhaustive search.

Therefore, we use the classic technique Meet-in-the-Middle for finding subsets whose sum is \(0\).

Algorithm

1. Precompute the list of primes and prime exponent vectors for \(1\sim 100\)

• Since \(P_i,Q_i\le 100\), only primes up to \(100\) are needed.
• Factorize each number and arrange the exponents in order of primes as a tuple of length \(m\).

2. Convert each card to a difference vector \(D_i\)

[ D_i[j]=\mathrm{vec}(P_i)[j]-\mathrm{vec}(Q_i)[j] ] (where \(j\) is the index of the prime)

This transforms the problem into “find a subset whose difference vectors sum to zero”.

3. Meet-in-the-Middle (split into left and right halves)

Split the cards into left \(L\) cards and right \(R\) cards (\(L=\lfloor N/2\rfloor\)).

For each half, enumerate all possible “vector sums” along with “the subset sizes that achieve them”.

In this implementation, for each vector sum: - We store “whether a subset of size \(k\) can produce this sum” as a bitset.

Trick of storing sizes as bits

For a given vector sum \(v\), prepare an integer mask where: - Bit \(k\) of mask is 1 ⇔ “there exists a subset of size \(k\) whose sum equals \(v\)”

When adding one more card, if we choose to include it, the size increases by 1, so the bitset is updated via mask << 1.

Using this, build_map constructs - map[vector] = size set (bitmask) in a DP fashion (two choices: “take” or “don’t take” each card).

4. Combine left and right halves to form zero-sum (composing sizes)

If the left half has sum \(v\) and the right half has sum \(-v\), then the total sum is zero.

Then, from: - The set of achievable sizes on the left maskL - The set of achievable sizes on the right maskR

we construct the total size set as [ {k+\ell \mid k\in L,\ \ell\in R} ] and find the minimum \(k+\ell\ge 2\) as the answer.

In the implementation, for each set bit \(k\) in maskL, we OR together maskR << k to compose the result (convolution accelerated via bit operations).

Finally, sizes \(0\) and \(1\) (empty set and single card selection) are forbidden, so they are excluded, and the position of the lowest set bit is the answer.

Complexity

• Time complexity:
  • Precomputation is negligible; the dominant term is the Meet-in-the-Middle part [ O\big(m\cdot 2^{N/2}\big) ] (where \(m\) is the number of primes, at most \(25\), and \(N\le 22\), so this is fast enough)
• Space complexity: [ O\big(2^{N/2}\big) ] (number of states stored in the dictionaries for each half)

Implementation Notes

• Do not handle products directly: The essence is to use prime exponent vectors (differences) and check for “sum equals zero”.

• Represent vectors as tuples to use them as dictionary keys (tuple is hashable).

• Compress size management into bitmasks to efficiently find the “minimum size”.

• The condition requires \(|S|\ge 2\), so sizes \(0\) and \(1\) must always be excluded from the final size set (in the code, this is done with totalmask &= ~3).

  Source Code

import sys

def sieve_primes_upto(n: int):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            step = i
            start = i * i
            is_prime[start:n + 1:step] = [False] * (((n - start) // step) + 1)
    return [i for i in range(2, n + 1) if is_prime[i]]

def build_map(diffs, m):
    zero = (0,) * m
    mp = {zero: 1}  # size 0
    limit_mask = (1 << (len(diffs) + 1)) - 1
    for d in diffs:
        nxt = dict(mp)
        for v, szmask in mp.items():
            nv = tuple(v[i] + d[i] for i in range(m))
            ns = (szmask << 1) & limit_mask
            nxt[nv] = nxt.get(nv, 0) | ns
        mp = nxt
    return mp

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    pairs = [(int(next(it)), int(next(it))) for _ in range(N)]

    primes = sieve_primes_upto(100)
    m = len(primes)

    fact = [None] * 101
    fact[0] = (0,) * m
    for x in range(1, 101):
        tmp = x
        vec = [0] * m
        for i, p in enumerate(primes):
            while tmp % p == 0:
                vec[i] += 1
                tmp //= p
            if tmp == 1:
                break
        fact[x] = tuple(vec)

    diffs = []
    for p, q in pairs:
        vp = fact[p]
        vq = fact[q]
        diffs.append(tuple(vp[i] - vq[i] for i in range(m)))

    n1 = N // 2
    left = diffs[:n1]
    right = diffs[n1:]

    mapL = build_map(left, m)
    mapR = build_map(right, m)

    full_mask = (1 << (N + 1)) - 1
    ans = 10**9
    for v, maskL in mapL.items():
        w = tuple(-x for x in v)
        maskR = mapR.get(w)
        if maskR is None:
            continue

        totalmask = 0
        tmp = maskL
        while tmp:
            lsb = tmp & -tmp
            k = lsb.bit_length() - 1
            totalmask |= (maskR << k)
            tmp -= lsb

        totalmask &= full_mask
        totalmask &= ~3  # remove sizes 0 and 1
        if totalmask:
            lsb = totalmask & -totalmask
            t = lsb.bit_length() - 1
            if t < ans:
                ans = t

    print(-1 if ans == 10**9 else ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.