[Codeforces Round #538(Div.2)] 1114F-Please, another Queries on Array?

题目就是维护区间积的欧拉欧拉欧拉欧拉欧拉欧拉函数辣~
注意到每个数最多也就 $300$，然后根据 $\varphi(n)=n\times \prod\limits_{i=1,p_i|n}(1-\frac{1}{p_i})$ 我们可以先筛出 $300$ 以内的素数，发现只有 $62$ 个，就可以用一个 long long 的状态来存这个区间有哪些素因子，然后就是普通的线段树维护辣~

#include <bits/stdc++.h>
#define ll long long
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define pb(x) push_back(x)
#define st(x) (1LL<<(x))
#define pii pair<int,int>
using namespace std;
const int N=400050;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
int n,q;
ll pri[300],inv[300];int tot,id[300];
ll a[N];
bool vis[300];
vector <int> f[305];
inline ll mi(ll a,ll b)
{
    
    while(b)
    {
        if(b&1)ret*=a,re
        a*=a,
        b>>=1;
    }
    return ret;
}
void shaipri()
{
    for(int i=2;i<=300;++i)
    {
        if(!vis[i])vis[i]=1,pri[++tot]=i,id[i]=tot;
        for(int j=1;j<=tot&&i*pri[j]<=300;++j)
        {
            vis[i*pri[j]]=1;
            if(
        }
    }
}
inline void fenjie(int x)
{
	int now=x;
    for(int i=1;i<=tot;++i)
    {
        if(
        {
            f[now].pb(i);
            while(
        }
    }
}
struct segtree
{
    int l,r;
    ll lazy,v;
    ll state,lazystate;
}t[N<<2];
inline void pushup(int id)
{
    t[id].v=(t[ls].v*t[rs].v
    t[id].state=(t[ls].state|t[rs].state);
}
inline void pushdown(int id)
{
    if(t[id].lazy!=1)
    {
        t[ls].v*=mi(t[id].lazy,(t[ls].r-t[ls].l+1LL)),t[ls].
        t[rs].v*=mi(t[id].lazy,(t[rs].r-t[rs].l+1LL)),t[rs].
        t[ls].lazy*=t[id].lazy,t[ls].laz
        t[rs].lazy*=t[id].lazy,t[rs].laz
        t[ls].state|=t[id].lazystate;
        t[rs].state|=t[id].lazystate;
        t[ls].lazystate|=t[id].lazystate;
        t[rs].lazystate|=t[id].lazystate;
        t[id].lazy=1;
        t[id].lazystate=0;
    }
}
void build(int l,int r,int id)
{
    t[id].lazy=1;t[id].l=l,t[id].r=r;
    if(l==r)
    {
        t[id].v=a[l];
        for(auto i:f[a[l]])t[id].state|=st(i-1);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    pushup(id);
}
void change(int id,int L,int R,ll x)
{
    int l=t[id].l,r=t[id].r;
    if(l>=L&&R>=r)
    {
        t[id].v*=mi(x,r-l+1),t[id].
        t[id].lazy*=x,t[id].laz
        for(auto i:f[x])
        {
            t[id].state|=(1LL<<(i-1));
            t[id].lazystate|=(1LL<<(i-1));
        }
        return;
    }
    pushdown(id);
    int mid=(l+r)>>1;
    if(R<=mid)change(ls,L,R,x);
    else if(L>mid)change(rs,L,R,x);
    else
    {
        change(ls,L,mid,x);
        change(rs,mid+1,R,x);
    }
    pushup(id);
}
ll querystate(int id,int L,int R)
{
    int l=t[id].l,r=t[id].r;
    if(l>=L&&r<=R)return t[id].state;
    pushdown(id);
    int mid=(l+r)>>1;
    if(R<=mid)return querystate(ls,L,R);
    else if(L>mid)return querystate(rs,L,R);
    else return (querystate(ls,L,mid)|querystate(rs,mid+1,R));
}
ll queryprod(int id,int L,int R)
{
    int l=t[id].l,r=t[id].r;
    if(l>=L&&r<=R)return t[id].v;
    pushdown(id);
    int mid=(l+r)>>1;
    if(R<=mid)return queryprod(ls,L,R);
    else if(L>mid)return queryprod(rs,L,R);
    else return (queryprod(ls,L,mid)*queryprod(rs,mid+1,R)
}
void Init()
{
    shaipri();
    for(int i=1;i<=300;++i)fenjie(i);
    for(int i=1;i<=tot;++i)
        inv[i]=mi(pri[i],mod-2);
}
char op[10];
int main()
{
    Init();
    scanf(
    for(int i=1;i<=n;++i)scanf(
    build(1,n,1);
    while(q--)
    {
        scanf(
        int l,r;scanf(
        if(op[0]=='M')
        {
            ll x;scanf(
            change(1,l,r,x);
        }
        else
        {
            ll state=querystate(1,l,r);
            ll x=queryprod(1,l,r);
            for(int i=1;i<=tot;++i)
            {
                if(state&(1LL<<(i-1)))
                    x=x*(pri[i]-1
            }
            printf(
        }
    }
    return 0;
}