33OJ
登录 注册

#P17638. [ICPC 2019 Yinchuan R] Pot!!

[ICPC 2019 Yinchuan R] Pot!!

题目描述

小 Q 非常困,他确实需要一些咖啡来提神。这时,小 L 拿来了一个壶,并这样描述这个壶:

对于一个质数 pp,若 pm∣np^m \mid n 且 pm+1∤np^{m+1} \nmid n,我们记 potp(n)=m\text{pot}_p(n)=m。

这个壶非常特别,它能立刻让所有人清醒过来。

现在小 L 向小 Q 提供了 n (1≤n≤105)n~(1 \le n \le 10^5) 个整数 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n,每个整数初始均为 11。之后,小 L 给出了 22 种操作:

  • MULTIPLY l r x:对于每个 i∈[l,r]i \in [l,r] (1≤l≤r≤n1\le l\le r\le n),将 aia_i 乘以 xx (2≤x≤102 \le x \le 10)。
  • MAX l r:计算$$\max_{l\le i\le r} \left\{ \max_{p|a_i} \left\{ \text{pot}_p (a_i) \right\} \right\}~(1 \le l \le r \le n),$$其中 pp 为质数。

现在你需要处理 q (1≤q≤105)q~(1 \le q \le 10^5) 个上述两种类型的操作。

如果你执行的是 “MULTIPLY” 操作,则无需输出任何内容。

如果你执行的是 “MAX” 操作,你需要输出一行形如 ANSWER y 的内容,其中 yy 为你计算出的值。

输入格式

第一行包含两个整数 n (1≤n≤105)n~(1 \le n \le 10^5) 和 q (1≤q≤105)q~(1 \le q \le 10^5),分别表示整数的个数和操作的个数。

接下来的 qq 行,每行包含一个上述类型的操作。

输出格式

对于每个 “MAX” 操作,输出一行形如 ANSWER y 的内容,其中 yy 为你计算出的值。

5 6
MULTIPLY 3 5 2
MULTIPLY 2 5 3
MAX 1 5
MULTIPLY 1 4 2 
MULTIPLY 2 5 5 
MAX 3 5
ANSWER 1
ANSWER 2

提示

若 mm 和 nn 均为非零整数,或更一般地,为整环中的非零元素,称 mm 整除 nn 当且仅当存在一个整数 kk(或整环中的元素 kk),使得 m×k=nm \times k = n,并记为 m∣nm \mid n。

翻译由 DeepSeek V4 Pro 完成