P17899 [ICPC 2026 Nanchang I] Little Z's Function
题目描述
小 Z 在高中曾经沉迷于欧拉函数 $\varphi$ (注:$\varphi(n)$ 表示不超过 $n$ 的正整数中与 $n$ 互质的数的个数。)等数论函数。
某一天,小 Z 打算和他的机器人朋友玩这样一个游戏:首先小 Z 会给出一个长度为 $n$ 的排列(注:一个长度为 $n$ 的排列是一个包含 $n$ 个整数的序列,其中 $1$ 到 $n$ 的每个整数恰好出现一次。例如,$[2,3,1,5,4]$ 是一个排列,而 $[1,2,2]$ 不是($2$ 出现了两次),$[1,3,4]$ 也不是($n=3$ 但出现了 $4$)。) $p$。随后小 Z
会多次向朋友提问,对于区间 $[l, r]$ ($1 \le l < r \le n$),最大的 $\varphi(p_i \times p_j)$
($l \le i < j \le r$) 的值是多少?
形式化地,对于每一组询问 $l, r$,你都需要计算:
$$
\max_{l \le i < j \le r} \varphi(p_i \times p_j)
$$
小 Z 已经解决了 $0$ 个询问,现在请你帮帮他,完成剩下的 $q$ 个询问的计算!
输入格式
第一行包含一个正整数 $n$ ($2 \le n \le 5 \times 10^5$),表示排列的长度。
第二行包含 $n$ 个互不相同的正整数 $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$),表示给定的排列 $p$。
第三行包含一个正整数 $q$ ($1 \le q \le 5 \times 10^5$),表示询问的个数。
接下来 $q$ 行,每行包含两个正整数 $l_i$ 和 $r_i$ ($1 \le l_i < r_i \le n$),表示第 $i$ 组询问的左右端点。
输出格式
对于每一组询问,输出一个整数,表示对应的最大值。