コンテンツにスキップ

DOJ Beginner Contest 11 G - Déjà vu

サイト
DOJ
コンテスト
DOJ Beginner Contest 11
問題
G - Déjà vu

正の整数列 a=(a1,a2,…,aN)a = (a_1, a_2, \dots, a_N) が与えられます。空でない部分列 bb に対して、次の操作を何回でも行えます。

  • 素数 pp を 1 つ選び、bb の要素のうち pp で割り切れるものをすべて同時に pp で割る。

bb の要素をすべて同じ値にするとき、その値の最大値を f(b)f(b) とします。すべての空でない部分列 bb についての f(b)f(b) の和を 998244353998244353 で割った余りを求める問題です。

ai≤2×105a_i \le 2 \times 10^5 で、NN の総和は 5×1055 \times 10^5 以下、max⁡a\max a の総和は 2×1052 \times 10^5 以下です。

素数 pp ごとに考えます。bb の各要素を素因数分解したときの pp の指数を見ると、pp を選ぶ操作は、正の指数をすべて 11 ずつ減らし、00 の指数はそのままにします。

最後にすべての指数を e>0e > 0 でそろえるには、正の指数どうしの差は変わらず、00 の指数は増えないので、はじめからすべての指数が ee でなければなりません。そうでなければ、すべて 00 にそろえるしかありません。

よって、f(b)f(b) は「bb のすべての要素で指数が等しい素数」について pep^e を掛けたものです。ここから次のことがいえます。

  • bb のすべての要素が c⋅jc \cdot j(gcd⁡(c,j)=1\gcd(c, j) = 1)の形で書ける   ⟺  \iff cc を割り切るどの素数についても、bb のすべての要素の指数が cc の指数と等しい   ⟺  \iff f(b)=c⋅df(b) = c \cdot d(gcd⁡(c,d)=1\gcd(c, d) = 1)と書ける

f(b)=cf(b) = c となる部分列の個数

Section titled “f(b)=cf(b) = cf(b)=c となる部分列の個数”

aa の要素のうち、c⋅jc \cdot j(gcd⁡(c,j)=1\gcd(c, j) = 1)の形のものの個数を tct_c とします。これらだけからなる空でない部分列は 2tc−12^{t_c} - 1 個あり、上の性質から、これはちょうど f(b)=c⋅jf(b) = c \cdot j(gcd⁡(c,j)=1\gcd(c, j) = 1)となる部分列全体です。f(b)=cf(b) = c となる部分列の個数を gcg_c とすると、

gc=2tc−1−∑j≥2, gcd⁡(c,j)=1gcjg_c = 2^{t_c} - 1 - \sum_{j \ge 2,\ \gcd(c, j) = 1} g_{cj}

です。cc の大きい順に計算すれば、右辺の gcjg_{cj} はすでに求まっています。答えは ∑cc⋅gc\sum_c c \cdot g_c です。

M=max⁡aM = \max a とすると、cc ごとに M/cM / c 個の倍数を見るので、全体で O(Mlog⁡M)O(M \log M) 回の gcd⁡\gcd 計算です。

Python
from math import gcd
MOD = 998244353
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
M = max(A)
tmp0 = [0] * (M + 1)
tmp1 = [0] * (M + 1)
for a in A:
tmp0[a] += 1
ans = 0
for i in reversed(range(1, M + 1)):
t = tmp0[i]
u = 0
for j in range(2, M // i + 1):
if gcd(i, j) != 1:
continue
t += tmp0[i * j]
u += tmp1[i * j]
v = (pow(2, t, MOD) - u - 1) % MOD
tmp1[i] = v
ans += i * v
ans %= MOD
print(ans)

tmp0[x] は値 xx の要素の個数、tmp1[c] は gcg_c です。t が tct_c、u が ∑gcj\sum g_{cj} にあたります。