ABC259E - LCM on Whiteboard

考え方

入力例1を表でまとめるとわかる．各$p$を横に並べ，$p$の指数を標柱に記入している．丸をつけているのは，各$p$の指数の最大値である．

$a_{i}$を1に変えた場合に最小公倍数が変化し得るのは「$a_{i}$の素因数$p$の指数$e$が，その他の$a_{j} \, (j \neq i)$の$p$の指数よりも大きいとき」である．

したがって，ナイーブには

• 各$p$に対し，指数の最大値とその個数を調べ，
• 指数の最大値に対応する$a_{i}$が1個だけのものの個数

とすれば良さそうである（最大値が2個以上あるときは最小公倍数は変わらない）．

ただし，

• 「すべての$a_{i}$が，何かしらの$p$で指数がmaxになる」か「$a_{i}$のなかで少なくとも１つ，どの$p$の指数でもmaxをとらないものがある」かで答えが1違ってくる
• 同じ$a_{i}$が複数の$p$の指数で最大となる場合がある（ダブルカウントしている場合は補正が必要）

ことに注意が必要．

回答例

from collections import defaultdict
N = int(input())
emax = defaultdict(int)
members = defaultdict(list)

for i in range(N):
    m = int(input())
    for _ in range(m):
        p, e = map(int, input().split())
        if e > emax[p]:
            members[p] = [(i, e)]
            emax[p] = e
        elif emax[p] == e:
            members[p].append((i, e))

ans = 0
cnt = [0] * N
for k in emax:
    num = len(members[k])
    if num == 1:
        ans += 1
        i, e = members[k][0]
        cnt[i] += 1

for i in range(N):
    if cnt[i] == 0:
        ans += 1
        break

for i in range(N):
    if cnt[i] > 1:
        ans -= cnt[i] - 1

print(ans)