コンテンツにスキップ

GCD

タグ「GCD」の記事 2 件

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} にあたります。

Blitz Round #25 C - Root Value

正の整数 xx に対して、xm\sqrt[m]{x} が自然数になるような最大の mm を f(x)f(x) とします。

長さ nn の数列 a1,…,ana_1, \ldots, a_n (2≤ai≤2002 \le a_i \le 200) と qq 個のクエリ (l,r)(l, r) が与えられるので、各クエリについて

f(∏i=lrai)f\left(\prod_{i=l}^{r} a_i\right)

を求める問題です。

  • 1≤n,q≤2⋅1051 \le n, q \le 2 \cdot 10^5、テストケースの nn の総和と qq の総和はそれぞれ 2⋅1052 \cdot 10^5 以下

正確な問題文は元の問題ページを見てください。

xx を素因数分解して x=p1e1p2e2⋯pkekx = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} とすると、xm\sqrt[m]{x} が整数になるのは、すべての指数 eje_j が mm の倍数のときです。したがって

f(x)=gcd⁡(e1,e2,…,ek)f(x) = \gcd(e_1, e_2, \ldots, e_k)

です。ai≥2a_i \ge 2 なので、積は 22 以上になり、指数のどれかは正になります。

積をそのまま計算すると巨大になりますが、指数だけを見れば足し算になります。ai≤200a_i \le 200 なので、現れる素数は 200200 以下の 4646 個だけです。各素数について指数の累積和を持っておけば、区間 [l,r][l, r] での各素数の指数は差を取るだけで求まり、その gcd⁡\gcd が答えです。

aia_i の上限を AA (=200= 200)、AA 以下の素数の個数を π(A)\pi(A) (=46= 46) とすると、計算量は O((n+q) π(A))O((n + q)\,\pi(A)) です。

Python
from math import gcd
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
for _ in range(int(input())):
N, Q = map(int, input().split())
A = list(map(int, input().split()))
acc = [[0] * len(prime)]
for a in A:
t = acc[-1].copy()
for i, p in enumerate(prime):
while a % p == 0:
t[i] += 1
a //= p
acc.append(t)
for _ in range(Q):
l, r = map(int, input().split())
l -= 1
ans = 0
for i in range(len(prime)):
ans = gcd(ans, acc[r][i] - acc[l][i])
print(ans)