题目链接
题目大意
两种操作
- 0 l r w, for each index i∈[l,r], change xi? to xi?×w.
- 1 l r, calculate and print
mod 998244353.
其中\varphi (x_{i}) 就是区间内欧拉函数的和
题目思路
要做这个题首先要知道以下两个定理
我们先预处理出来一百以内的欧拉函数
以及一百以内的每个数 所包含的质因数的数量
然后去建树 这棵树由于要维护区间乘
因此我有一个laz标记 由于还需要判断某个质因子是否存在 因此我在每一个节点都用一个bitset来记录 （当然这个bitset也可以用int判断）
那么这棵树就可以写为如下
struct node{ll sum;ll laz;bitset<30>tag;
}ans[maxn*4];值得注意的地方就是updata操作 每次操作只区间操作一个质因数
分为三种情况
1如果当前区间 都有该质因数 那么直接用开头给出的定理2计算答案
2如果当前区间没有该质数那么就继续向下updata
3直到当前的区间只是一个点并且没有该质数 这个时候就根据开头给出的定理1计算答案并且将该节点的bitset 加上该质数
这里计算到每个节点并且还不会超时的原因就是 如果该节点对于该质数已经进行过一次3操作
就不会进行第二次
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
const int MOD=998244353;
const int maxn=1e5+10;
const int M=105;
typedef pair<int,int> PII;
ll a[maxn];
int euler[M],prime[M];//一百以内欧拉函数和 质数
bool vis[M];
int cnt[M][30];//cnt[i][j]代表i有几个质数prime[j]
bitset <30> st[M];//m以内的这个数的某个质数是否存在
ll qpow(ll a,ll b){ll res = 1;while(b){if(b&1) res = res * a % MOD;a = a * a % MOD;b >>= 1;}return res;
}
void getPrime(){for(int i = 2;i < M;i++){if(!vis[i]){prime[++prime[0]] = i;euler[i] = i-1;}for(int j = 1;j <= prime[0] && (ll)prime[j]*i < M;j++){int tp = prime[j]*i;vis[tp] = 1;if(i%prime[j] == 0){euler[tp] = euler[i] * prime[j];break;}euler[tp] = euler[i]*(prime[j]-1);}}euler[1] = 1;
}
ll ls(ll x)
{return x<<1;
}
ll rs(ll x)
{return x<<1|1;
}
struct node{ll sum;ll laz;bitset<30>tag;
}ans[maxn*4];
ll n,m;
void pushup(ll x)
{ans[x].sum=ans[ls(x)].sum+ans[rs(x)].sum;ans[x].sum%=mod;ans[x].tag=ans[ls(x)].tag&ans[rs(x)].tag;
}
void build(ll x,ll l,ll r)
{ans[x].laz=1;if(l==r){ans[x].sum=euler[a[l]];ans[x].tag=st[a[l]];return ;}ll mid=(l+r)/2;build(ls(x),l,mid);build(rs(x),mid+1,r);pushup(x);
}
void pushdown(ll x,ll l,ll r)
{if(ans[x].laz==1)return ;ans[ls(x)].laz=ans[ls(x)].laz*ans[x].laz%mod;ans[rs(x)].laz=ans[rs(x)].laz*ans[x].laz%mod;ans[ls(x)].sum=ans[ls(x)].sum*ans[x].laz%mod;ans[rs(x)].sum=ans[rs(x)].sum*ans[x].laz%mod;ans[x].laz=1;
}
void updata(ll l,ll r,ll nl,ll nr,ll x,PII p)//fisrt和second 是质数编号和质数次数
{if(nl>=l&&nr<=r&&ans[x].tag[p.first]==1){ans[x].sum=ans[x].sum*qpow(prime[p.first],p.second)%mod;ans[x].laz=ans[x].laz*qpow(prime[p.first],p.second)%mod;return ;}else if(nl==nr)//到了修改单个节点的时候并且该素数没有 {ans[x].tag[p.first]=1;ans[x].sum=ans[x].sum*(prime[p.first]-1)%mod;ans[x].sum=ans[x].sum*(qpow(prime[p.first],p.second-1))%mod;return ;}else {pushdown(x,nl,nr);ll mid=(nl+nr)/2;if(mid>=l){updata(l,r,nl,mid,ls(x),p);}if(mid<r){updata(l,r,mid+1,nr,rs(x),p);}pushup(x);}
}
ll query(ll l,ll r,ll nl,ll nr,ll x)
{ll mid=(nl+nr)/2;if(nl>=l&&nr<=r){return ans[x].sum%mod;}pushdown(x,nl,nr);ll tans=0;if(mid>=l)tans+=query(l,r,nl,mid,ls(x));if(mid<r)tans+=query(l,r,mid+1,nr,rs(x));pushup(x);return tans%mod;
}
int main()
{getPrime();for(int i = 1;i < M;i++){for(int j = 1;j <= prime[0];j++) {int x = i;while(x % prime[j] == 0) cnt[i][j]++,x /= prime[j];st[i][j] = cnt[i][j];}}cin>>n>>m;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);} build(1,1,n);int op;ll l,r,x;for(int i=1;i<=m;i++){scanf("%d",&op);if(op){scanf("%lld %lld",&l,&r);cout<<query(l,r,1,n,1)<<endl;}else {scanf("%lld %lld %lld",&l,&r,&x);for(int j=1;j<=prime[0];j++)if(cnt[x][j])//对于x的每一个质数都进行更新 updata(l,r,1,n,1,{j,cnt[x][j]});}}return 0;
}