問題
$N$ 個の整数 $a_1, \ldots, a_N$（各 $a_i \le 10^6$）に対し $Q$ 個のクエリを処理せよ：
update i x: $a_i$ を $x$ に変更するquery l r: $\prod_{k=l}^{r} \phi(a_k) \bmod (10^9+7)$ を出力せよ（$\phi$: オイラーのトーシェント関数）
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $1 \le N \le 10^5$ |
| $Q$ | $1 \le Q \le 10^5$ |
| $a_i, x$ | $1 \le a_i, x \le 10^6$ |
入出力例
入力例 1
5 3
6 4 10 15 7
query 1 3
update 2 9
query 1 5出力例 1
16
96φ(6)=2, φ(4)=2, φ(10)=4 → 2×2×4=16。更新後: φ(6)=2, φ(9)=6, φ(10)=4, φ(15)=8, φ(7)=6 → 2×6×4×8×... (1〜5の積)。
概念図: 線形篩 + 積セグメント木
ヒント（段階的開示）
ヒント1: 方向性
オイラーのトーシェント関数 $\phi(n)$ は乗法的関数。セグメント木の各ノードに区間積 $\prod \phi(a_i) \bmod (10^9+7)$ を保持し、点更新・区間クエリを O(log N) で処理する。$\phi$ の値は 1〜10^6 の全値を線形篩で前計算する。
ヒント2: アプローチ
- 線形篩で $1 \le x \le 10^6$ の全 $\phi(x)$ を前計算（O(MAX) 前処理）
- セグメント木に $\phi(a_i)$ の値を格納し、積モノイドでクエリ
update i x: $\phi(x)$ の値を計算してセグメント木を点更新 O(log N)query l r: 区間積を返す O(log N)
ヒント3: コード骨格
# 線形篩で phi を前計算（エラトステネス変形）
def euler_phi_sieve(MAX):
phi = list(range(MAX))
for i in range(2, MAX):
if phi[i] == i: # i は素数
for j in range(i, MAX, i):
phi[j] -= phi[j] // i
return phi
PHI = euler_phi_sieve(10**6 + 1)
# 積 SegTree
class SegTree:
def __init__(self, data, mod): ...
def update(self, i, val): ...
def query(self, l, r): ...模範解答 (Python)
import sys
input = sys.stdin.readline
MOD = 10**9 + 7
MAX = 10**6 + 1
def euler_phi_sieve(MAX):
phi = list(range(MAX))
for i in range(2, MAX):
if phi[i] == i: # i は素数
for j in range(i, MAX, i):
phi[j] -= phi[j] // i
return phi
PHI = euler_phi_sieve(MAX)
class SegTree:
def __init__(self, data, mod):
self.n = len(data)
self.mod = mod
self.tree = [1] * (2 * self.n)
for i, v in enumerate(data):
self.tree[self.n + i] = v % mod
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[2*i] * self.tree[2*i+1] % mod
def update(self, i, val):
i += self.n
self.tree[i] = val % self.mod
i >>= 1
while i:
self.tree[i] = self.tree[2*i] * self.tree[2*i+1] % self.mod
i >>= 1
def query(self, l, r): # 1-indexed [l, r]
l += self.n - 1; r += self.n
res = 1
while l < r:
if l & 1:
res = res * self.tree[l] % self.mod
l += 1
if r & 1:
r -= 1
res = res * self.tree[r] % self.mod
l >>= 1; r >>= 1
return res
def solve():
N, Q = map(int, input().split())
A = list(map(int, input().split()))
phi_vals = [PHI[a] for a in A]
seg = SegTree(phi_vals, MOD)
out = []
for _ in range(Q):
line = input().split()
if line[0] == 'update':
i, x = int(line[1]), int(line[2])
seg.update(i - 1, PHI[x])
else:
l, r = int(line[1]), int(line[2])
out.append(str(seg.query(l, r)))
print('\n'.join(out))
solve()Step-by-Step 解説
Step 1: オイラーのトーシェント関数 φ(n)
$$\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$
乗法的関数（$\gcd(m,n)=1 \Rightarrow \phi(mn) = \phi(m)\phi(n)$）。線形篩の核心：各数を最小素因数で一度だけ篩う。
- $p \nmid i$ のとき $\phi(ip) = \phi(i)(p-1)$
- $p \mid i$ のとき $\phi(ip) = \phi(i) \cdot p$
Step 2: 積セグメント木
各ノードに区間 $[l, r]$ の $\prod \phi(a_i) \bmod (10^9+7)$ を保持。点更新 O(log N)・区間クエリ O(log N)。モノイドは (×, 単位元=1)。
Step 3: update クエリ
$a_i$ を $x$ に変えたとき、PHI[x] を計算してセグメント木の $i$ 番ノードを更新。
Step 4: 乗法的関数の性質の利用
$\phi$ は乗法的なので、GCD 畳み込みや Dirichlet 積への拡張も可能。例えば $\sum_{d \mid n} \phi(d) = n$（Dirichlet 積 $\phi * \mathbf{1} = \text{id}$）という関係を利用した問題が赤色レベルで頻出。
Step 5: 計算量
| 処理 | 計算量 |
|---|---|
| φ 前計算（線形篩） | $O(\text{MAX})$ |
| SegTree 構築 | $O(N)$ |
| update クエリ | $O(\log N)$ |
| range product クエリ | $O(\log N)$ |
| 全体 | $O(\text{MAX} + N + Q \log N)$ |
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| φ(1) = 1 の確認 | 篩の初期化で phi[1] = 0 になる | phi = list(range(MAX)) で phi[1]=1 |
| 1-indexed ↔ 0-indexed の混在 | query/update で -1 忘れ | SegTree 内で統一的に変換 |
| 掛け算後に mod を取り忘れる | 値が巨大になり遅くなる | 各掛け算直後に % MOD |
次のステップ
発展問題: 区間内の $\sum \mu(a_k)$（メビウス関数の和）と $\sum \phi(a_k)$ の両方をオンラインクエリで答えよ。Dirichlet 積 $\phi * \mathbf{1} = \text{id}$ の関係を用いて高速化できるか検討せよ。