累積和 | shogo314 のブログ

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)

Blitz Round #25 B - Jump Trip Score

2026年10月4日

問題の概要

長さ $n$ の整数列 $a_1, \ldots, a_n$ があり、位置 $i = 1$ から出発して $i = n + 1$ に着いたら終わりです。スコアは $0$ から始まり、各位置で次のどちらかを行います。

$a_i$ をスコアに足して $i + 1$ に進む
正の整数 $d$ ( $i + d \le n + 1$ ) を選んで $i + d$ に跳ぶ(スコアは変わらない)

跳ぶ操作は高々 1 回まで使えるとき、最終スコアの最大値を求める問題です。

$1 \le n \le 4 \cdot 10^5$ 、 $-10^9 \le a_i \le 10^9$ 、テストケースの $n$ の総和は $4 \cdot 10^5$ 以下

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

解法

$i$ から $i + d$ に跳ぶと、 $a_i, \ldots, a_{i+d-1}$ を飛ばすことになります。跳ぶのは高々 1 回なので、得られるスコアは

(\text{先頭からの連続部分の和}) + (\text{末尾までの連続部分の和})

で、間の 1 区間を飛ばした形になります(跳ばなければ全部の和)。

そこで

$L_k$ = 長さ $k$ 以下の接頭辞の和の最大値(空も含むので $0$ 以上)
$R_k$ = 位置 $k + 1$ 以降から始まる接尾辞の和の最大値(空も含む)

を累積和で求めておけば、答えは

\max_{0 \le k \le n} (L_k + R_k)

です。接頭辞と接尾辞が重ならないように、境目 $k$ を全通り試しています。計算量は $O(n)$ です。

解答コード

Python

for _ in range(int(input())):
    N = int(input())
    A = list(map(int,input().split()))
    dp0 = [0]
    x = 0
    for a in A:
        x += a
        dp0.append(max(x, dp0[-1]))
    dp1 = [0]
    x = 0
    for a in reversed(A):
        x += a
        dp1.append(max(x, dp1[-1]))
    dp1.reverse()
    print(max(x+y for x,y in zip(dp0,dp1)))

dp0 が $L$ 、dp1 が $R$ にあたります。