题目链接：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
2# Note
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。 由于每个质因子是独立的，所以我们可以考虑将所有操作离线，分别处理每个质因子，这样就只需要开一个了。但是由于种种原因（似乎是线段树的常数太大），我是用两个树状数组完成区间加和查询区间和的。
# 代码
# 方法一
| |
# 方法二
| |