概要

各カード \(i\) について「表の素因数指数ベクトル − 裏の素因数指数ベクトル」を作り、選んだ集合 \(S\) でそれらの総和が \(0\) になるか（なれば積が等しい）を Meet-in-the-Middle で判定し、さらに \(|S|\) の最小値を求めます。

考察

重要な気づき：積の等しさは「素因数指数の和」で判定できる

条件 [ \prod_{i\in S} Pi=\prod{i\in S} Q_i ] は、両辺を素因数分解して各素数の指数を比べればよいです。

例えば素数 \(2,3,5,\dots\) について、ある数 \(x\) の素因数指数ベクトルを [ \mathrm{vec}(x)=(e_2,e_3,e_5,\dots) ] とすると、 [ \mathrm{vec}\Big(\prod x\Big)=\sum \mathrm{vec}(x) ] が成り立ちます（指数が足し算になる）。

よって各カードに対して [ D_i=\mathrm{vec}(P_i)-\mathrm{vec}(Qi) ] を作ると、条件は [ \sum{i\in S} D_i=\mathbf{0} ] に等価です。

素朴に全部試すのが難しい理由

• \(S\) の候補は \(2^N\) 個（最大 \(2^{22}\approx 4.2\times 10^6\)）。
• さらに積を直接扱うと巨大になりオーバーフローや計算コストの問題が出ます（Pythonでも大きな整数は遅い）。
• 「最小の \(|S|\)」まで求めるとなると、全探索しつつサイズ管理も必要になります。

そこで「和が \(0\) になる部分集合」を探す典型手法である Meet-in-the-Middle を使います。

アルゴリズム

1. 素数リストと \(1\sim 100\) の素因数指数ベクトルを前計算

• \(P_i,Q_i\le 100\) なので、必要な素数は \(100\) 以下のみ。
• それぞれを素因数分解して、素数の順に指数を並べたタプル（長さ \(m\)）にします。

2. 各カードを差分ベクトル \(D_i\) に変換

[ D_i[j]=\mathrm{vec}(P_i)[j]-\mathrm{vec}(Q_i)[j] ] （\(j\) は素数の番号）

これで「選んだ差分ベクトルの和がゼロ」問題になります。

3. Meet-in-the-Middle（左右に分割）

カードを左 \(L\) 枚、右 \(R\) 枚に分けます（\(L=\lfloor N/2\rfloor\)）。

それぞれについて「作れるベクトルの和」と「そのときの部分集合サイズ」を列挙します。

ただし本実装では、各ベクトル和ごとに - 「サイズ \(k\) の部分集合が作れるか」を ビット集合 で持ちます。

サイズをビットで持つ工夫

あるベクトル和 \(v\) に対して整数 mask を用意し、 - mask の \(k\) ビット目が 1 ⇔ 「サイズ \(k\) の部分集合で和が \(v\) になるものが存在する」

とします。

カードを1枚追加すると、選ぶ場合はサイズが +1 されるので、ビット集合は mask << 1 で更新できます。

これを使って build_map では - map[vector] = サイズ集合(ビットマスク) をDP的に構築します（「取る/取らない」の2択）。

4. 左右を突き合わせてゼロ和を作る（サイズも合成）

左で和が \(v\)、右で和が \(-v\) なら全体の和はゼロです。

あとは - 左で可能なサイズ集合 maskL - 右で可能なサイズ集合 maskR から、全体サイズ集合を [ {k+\ell \mid k\in L,\ \ell\in R} ] として作り、最小の \(k+\ell\ge 2\) を答えます。

実装では、maskL の立っているビット \(k\) ごとに maskR << k を OR して合成しています（畳み込みをビット演算で高速化）。

最後にサイズ \(0,1\)（空集合・1枚選択）は禁止なので除外し、最小ビット位置が答えです。

計算量

• 時間計算量:
  
  • 前計算は小さいので無視でき、支配項は Meet-in-the-Middle 部分
    [ O\big(m\cdot 2^{N/2}\big) ] （\(m\) は素数個数で最大 \(25\)、\(N\le 22\) なので十分高速）
• 空間計算量:
  [ O\big(2^{N/2}\big) ] （左右の辞書に入る状態数）

実装のポイント

• 積を直接扱わない：素因数指数ベクトル（差分）にして「和がゼロ」を見るのが本質。

• ベクトルはタプルにして辞書キーにする（tuple は hashable）。

• サイズ管理をビットマスクで圧縮すると、「最小サイズ」を高速に求められる。

• 条件は \(|S|\ge 2\) なので、最終的なサイズ集合から \(0\) と \(1\) を必ず除外する（コードでは totalmask &= ~3）。

  ソースコード

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()

---

この解説は gpt-5.2-high によって生成されました。