GCD

タグ「GCD」の記事 1 件

Blitz Round #25 C - Root Value

2026年10月4日

問題の概要

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

長さ $n$ の数列 $a_1, \ldots, a_n$ ($2 \le a_i \le 200$) と $q$ 個のクエリ $(l, r)$ が与えられるので、各クエリについて

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

を求める問題です。

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

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

解法

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

$$f(x) = \gcd(e_1, e_2, \ldots, e_k)$$

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

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

$a_i$ の上限を $A$ ($= 200$)、$A$ 以下の素数の個数を $\pi(A)$ ($= 46$) とすると、計算量は $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)

タグ:

• 素因数分解
• 累積和
• GCD