DOJ Beginner Contest 11 G - Déjà vu
- サイト
- DOJ
- コンテスト
- DOJ Beginner Contest 11
- 問題
- G - Déjà vu
正の整数列 が与えられます。空でない部分列 に対して、次の操作を何回でも行えます。
- 素数 を 1 つ選び、 の要素のうち で割り切れるものをすべて同時に で割る。
の要素をすべて同じ値にするとき、その値の最大値を とします。すべての空でない部分列 についての の和を で割った余りを求める問題です。
で、 の総和は 以下、 の総和は 以下です。
素数 ごとに考えます。 の各要素を素因数分解したときの の指数を見ると、 を選ぶ操作は、正の指数をすべて ずつ減らし、 の指数はそのままにします。
最後にすべての指数を でそろえるには、正の指数どうしの差は変わらず、 の指数は増えないので、はじめからすべての指数が でなければなりません。そうでなければ、すべて にそろえるしかありません。
よって、 は「 のすべての要素で指数が等しい素数」について を掛けたものです。ここから次のことがいえます。
- のすべての要素が ()の形で書ける を割り切るどの素数についても、 のすべての要素の指数が の指数と等しい ()と書ける
の要素のうち、()の形のものの個数を とします。これらだけからなる空でない部分列は 個あり、上の性質から、これはちょうど ()となる部分列全体です。 となる部分列の個数を とすると、
です。 の大きい順に計算すれば、右辺の はすでに求まっています。答えは です。
とすると、 ごとに 個の倍数を見るので、全体で 回の 計算です。
Python
from math import gcd
MOD = 998244353for _ 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] は値 の要素の個数、tmp1[c] は です。t が 、u が にあたります。