题目链接：Codeforces Round #538 (Div. 2) - Problem F
描述
You are given an array $a_1, a_2, \ldots, a_n$.
You need to perform $q$ queries of the following two types:
"MULTIPLY l r x"— for every $i$ ($l \le i \le r$) multiply $a_i$ by $x$."TOTIENT l r"— print$\varphi(\prod \limits_{i=l}^{r} a_i)$ taken modulo $10^9+7$, where $\varphi$ denotes Euler’s totient function. The Euler’s totient function of a positive integer $n$ (denoted as $\varphi(n)$) is the number of integers $x$ ($1 \le x \le n$) such that $\gcd(n,x) = 1$
Input
The first line contains two integers $n$ and $q$ ($1 \le n \le 4 \cdot 10^5$, $1 \le q \le 2 \cdot 10^5$) — the number of elements in array $a$ and the number of queries.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 300$) — the elements of array $a$.
Then $q$ lines follow, describing queries in the format given in the statement.
"MULTIPLY l r x" ($1 \le l \le r \le n$, $1 \le x \le 300$) — denotes a multiplication query.
"TOTIENT l r" ($1 \le l \le r \le n$) — denotes a query on the value of Euler’s totient function.
It is guaranteed that there is at least one "TOTIENT" query.
Output
For each "TOTIENT" query, print the answer to it.
Example
Input
4 4
5 9 1 2
TOTIENT 3 3
TOTIENT 3 4
MULTIPLY 4 4 3
TOTIENT 4 4Output
1
1
2Note
In the first example, $\varphi(1) = 1$ for the first query, $\varphi(2) = 1$ for the second query and $\varphi(6) = 2$ for the third one.
思路
首先我们知道：若 $n = \prod\limits_{i = 1} ^ r p_i^{k_i}$，则 $\varphi(n) = \prod\limits_{i = 1} ^ r p_i ^ {k_i - 1} (p_i - 1) = n \prod\limits_{p | n}(1 - \frac{1}{p})$。其中 $p$ 是质数。
方法一：根据最后的式子，我们只需要维护两个量：区间的乘积、区间的质因子。这可以分别使用两个线段树来维护和合并信息。由于 $300$ 内一共有 $62$ 个质数（打表可知），所以可以使用
long long来压状态。然后就是正常的线段树打标记没什么好说的了。方法二：根据前面一个式子，我们可以分别维护每个质因子的个数来计算其对答案的贡献。这样需要开 $62$ 个线段树，妥妥MLE。 由于每个质因子是独立的，所以我们可以考虑将所有操作离线，分别处理每个质因子，这样就只需要开一个了。但是由于种种原因（似乎是线段树的常数太大），我是用两个树状数组完成区间加和查询区间和的。
代码
方法一
| |
方法二
| |