原题链接 F. Please, another Queries on Array?
这道题让求\(\phi(\prod\limits_{i = l}^r a_i)\),然后我们化简一下。
设\(P\)是\(\prod\limits_{i = l}^r a_i\)质因子的集合，那么化简得：
\[\phi(\prod\limits_{i = l}^r a_i) = \prod\limits_{i = l}^r a_i \times \prod\limits_{p \in P} \cfrac{p-1}{p}
\]
因此我们分成两部分计算，前边部分\(\prod\limits_{i = l}^r a_i\)很容易维护，后边部分
\(\prod\limits_{p \in P} \cfrac{p-1}{p}\)，我们知道一个数的欧拉函数只与有几个质因子有关，而\(300\)以内的质数只有\(62\)个，所有我们每次修改的时候只需要暴力枚举\(62\)个质数，然后状压存储即可。
// Problem: F. Please, another Queries on Array?
// Contest: Codeforces - Codeforces Round #538 (Div. 2)
// URL: https://codeforces.com/contest/1114/problem/F
// Memory Limit: 256 MB
// Time Limit: 5500 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 4E5 + 10;
const LL Mod = 1e9 + 7;
int a[N];
int primes[310], cnt = 0, st[310];
char op[10];
void get_primes(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) primes[cnt++] = i;
for (int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = 1;
if (i % primes[j] == 0) break;
}
}
}
struct SegMentTree {
int l, r;
LL products, mul, OR, tag;
}tr[N * 4];
LL qmi(LL a, LL b, LL p) {
LL res = 1ll;
while (b) {
if (b & 1) res = res * a % p;
b >>= 1;
a = a * a % p;
}
return res;
}
void pushup(int u) {
tr[u].products = tr[u << 1].products * tr[u << 1 | 1].products % Mod;
tr[u].OR = tr[u << 1].OR | tr[u << 1 | 1].OR;
}
void pushdown(int u) {
if (tr[u].mul == 1 || !tr[u].tag) return;
auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
left.mul = left.mul * root.mul % Mod; right.mul = right.mul * root.mul % Mod;
left.products = left.products * qmi(root.mul, left.r - left.l + 1, Mod) % Mod;
right.products = right.products * qmi(root.mul, right.r - right.l + 1, Mod) % Mod;
left.tag = left.tag | root.tag; right.tag = right.tag | root.tag;
left.OR = left.OR | root.tag; right.OR = right.OR | root.tag;
root.mul = 1; root.tag = 0;
}
void build(int u, int l, int r) {
if (l == r) {
tr[u] = {l, r, 1ll * a[l], 1ll};
for (int i = 0; i < cnt; i++) {
if (a[l] % primes[i] == 0) {
tr[u].OR |= (1ll << i);
}
}
} else {
tr[u].l = l, tr[u].r = r, tr[u].mul = 1ll;
//tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, LL p, int x) {
if (l <= tr[u].l && tr[u].r <= r) {
tr[u].mul = tr[u].mul * 1ll * x % Mod;
tr[u].products = tr[u].products * qmi(1ll * x, 1ll * (tr[u].r - tr[u].l + 1), Mod) % Mod;
tr[u].OR |= p, tr[u].tag |= p;
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, p, x);
if (r > mid) modify(u << 1 | 1, l, r, p, x);
pushup(u);
}
LL ask(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) {
return tr[u].products;
}
pushdown(u);
LL res = 1ll;
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) res = res * ask(u << 1, l, r) % Mod;
if (r > mid) res = res * ask(u << 1 | 1, l, r) % Mod;
return res;
}
int ask_flag(int u, int l, int r, int i) {
if (l <= tr[u].l && tr[u].r <= r) {
return (tr[u].OR >> i & 1);
}
pushdown(u);
LL res = 0ll;
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) res += ask_flag(u << 1, l, r, i);
if (r > mid) res += ask_flag(u << 1 | 1, l, r, i);
return res;
}
int main() {
get_primes(300);
//cout << cnt << endl;
int n, q;
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
build(1, 1, n);
while (q--) {
int l, r, x;
//cin >> s;
scanf("%s%d%d", &op, &l, &r);
if (op[0] == 'M') {
scanf("%d", &x);
LL p = 0;
for (int i = 0; i < cnt; i++) {
if (x % primes[i] == 0) {
p |= (1ll << i);
}
}
modify(1, l, r, p, x);
} else if (op[0] == 'T') {
LL res = ask(1, l, r);
for (int i = 0; i < cnt; i++) {
int p = primes[i];
if (ask_flag(1, l, r, i)) {
res = res * (p - 1) % Mod;
res = res * qmi(p, Mod - 2, Mod) % Mod;
}
}
printf("%lld\n", res);
}
}
return 0;
}