链接
大意
每次给你两种操作，一种是区间乘，另一种是求ph[a[l]]+ph[a[l+1]]...+ph[a[r]]ph[a[l]] + ph[a[l+1]]...+ph[a[r]]ph[a[l]]+ph[a[l+1]]...+ph[a[r]]
思路
首先，观察到区间乘是套了一个函数的，所以我们不能直接乘，得想办法把这个化简一下
我们知道对于欧拉函数有这么一个性质, 当p是质数时
- p不是x的因子时，ph(p?x)=p?ph(x)ph(p*x)=p*ph(x)ph(p?x)=p?ph(x)
- p是x的因子时，ph(p?x)=(p?1)?ph(x)ph(p*x)=(p-1)*ph(x)ph(p?x)=(p?1)?ph(x)
所以给每段区间乘www之前，需要先分解w，可以先打一个表，保存1-100的所有结果。
这样就成功把这个p从提取到了外面，但是不知道每次是乘(p-1)还是p，所以我们需要加一个状态st，表示这个区间有没有某个因子。100以内的质数不超过25个，所以只需要用一个int表示有没有某个因子就行了。某一位为1时，表示有这个质因子。
更新操作：
- 当区间[l,r][l,r][l,r]都有因子p时，给这个区间打上一个乘法标记，更新sum。
- 否则则递归更新左右儿子
进行25?10525* 10^525?105 次，所有叶子节点都会包含了100以内的所有质数，所以复杂度完全ok
代码
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 1e5 + 10, M = N + N, B = 4, P = 998244353, INF = 1e9 + 10;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
using tp = tuple<int,int,int,int>;
bool muti = false;int n, m;
int pr[N], phi[N], cnt;int prid[200];
//存分解后的数字
vector<int> fac[200];
bool st[N];
int a[N];struct Node
{
int l, r;LL mul, sum;//质数状态int st;
}tr[N << 2];void get_primes(int n) {
phi[1] = 1;for(int i = 2; i <= n; i++) {
if(!st[i]) pr[cnt++] = i, phi[i] = i - 1, prid[i] = cnt - 1;for(int j = 0; pr[j] * i <= n; j++) {
st[pr[j] * i] = true;if(i % pr[j] == 0) {
phi[pr[j] * i] = pr[j] * phi[i];break;}phi[pr[j] * i] = (pr[j] - 1) * phi[i];}}
}
void pushup(int u) {
tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % P;tr[u].st = tr[u << 1].st & tr[u << 1 | 1].st;
}void pushdown(int u) {
if(tr[u].mul > 1) {
LL& v = tr[u].mul;auto& lch = tr[u << 1], &rch = tr[u << 1 | 1];lch.sum = lch.sum * v % P, lch.mul = lch.mul * v % P;rch.sum = rch.sum * v % P, rch.mul = rch.mul * v % P;v = 1;}
}void build(int u, int l, int r) {
tr[u] = {
l, r, 1ll};if(l == r) {
tr[u].sum = phi[a[l]];for(int x: fac[a[l]]) tr[u].st |= 1 << prid[x];return;}int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);
}
void printNode(int u) {
auto rt = tr[u];printf("[%d, %d], sum=%lld, mul=%lld, st=%d\n\n", tr[u].l, tr[u].r, rt.sum, rt.mul, rt.st);
}
//区间乘操作
void update(int u, int l, int r, int val) {
if(tr[u].l == tr[u].r) {
if(tr[u].st & (1 << prid[val])) tr[u].sum = tr[u].sum * val % P;else tr[u].sum = tr[u].sum * (val - 1) % P;tr[u].st |= 1 << prid[val];return;}if(tr[u].l >= l && tr[u].r <= r) {
if(tr[u].st & (1 << prid[val])) {
tr[u].mul = tr[u].mul * val % P;tr[u].sum = tr[u].sum * val % P;}else {
//更新左右子树pushdown(u);update(u << 1, l, r, val), update(u << 1 | 1, l, r, val);pushup(u);}return;}int mid = tr[u].l + tr[u].r >> 1;pushdown(u);if(l <= mid) update(u << 1, l, r, val);if(r > mid) update(u << 1 | 1, l, r, val);pushup(u);
}
int query(int u, int l, int r) {
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;int mid = tr[u].l + tr[u].r >> 1;int res = 0;pushdown(u);if(l <= mid) res = query(u << 1, l, r);if(r > mid) res += query(u << 1 | 1, l, r); return res % P;
}
void solve() {
get_primes(100);for(int i = 2; i <= 100; i++) {
int x = i;for(int j = 0; j < cnt && pr[j] * pr[j] <= x; j++) {
int c = 0;while(x % pr[j] == 0) {
c++;x /= pr[j];fac[i].push_back(pr[j]);}}if(x > 1) fac[i].push_back(x);}cin >> n >> m;for(int i = 1; i <= n; i++) cin >> a[i];build(1, 1, n);while(m--) {
int t, l, r, w;cin >> t >> l >> r;if(!t) {
cin >> w;for(int x: fac[w]) update(1, l, r, x);}else cout << query(1, l, r) << endl;}
}int main()
{
#ifdef ONLINE_JUDGE
#else freopen("L.txt", "r", stdin);
#endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int T = 1;if(muti) cin >> T;while (T--) solve();return 0;
}