CF1114F Please, another Queries on Array?

CF1114F Please, another Queries on Array?

题目大意

你有一个数组\(a_1,a_2,\dots,a_n\)。

现在你需要完成\(q\)次操作，有以下两种操作形式：

1. MULTIPLY l r x，对于所有\(i(l\le i\le r)\)，将\(a_i\)乘上\(x\)。

2. TOTIENT l r，求出\(\varphi(\prod_{i=l}^ra_i)\)，对\(10^9+7\)取模后的结果。其中\(\varphi\)表示欧拉函数，\(\varphi(n)\)的定义为\(1\dots n\)中与\(n\)互质的数的个数。

分析

总的来说还是蛮简单的。

我们来速度分析一下，我们需要算\(\phi(\prod_{i=l}^{r}a_i)\)，我们知道计算\(\phi(x)\)的式子,\(\phi(x)=a\prod_{p|x,p为质数}(1-\frac{1}{p})\)

因此，我们计算上式就要知道两个东西

• \(a_l\)到\(a_r\)的积
• \(a_l\)到\(a_r\)的积的所有质数

我们可以通过离线计算一下，由于\(a_i\leq300\)，因此最多有62个质因子。则直接考虑状压表示。

这题最麻烦的是各种细节，提醒我们写线段树一定要小心再小心。

Ac_code

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
typedef long long LL;
const int N = 4e5 + 10,mod = 1e9 + 7;
struct Node
{
    int l,r;
    int sum,mul;//维护区间积，与区间积的懒标记
    LL st,cov;//维护区间积的所有质因子，与区间积所有质因子的懒标记
}tr[N<<2];

int n,q;
int a[N],b[70],inv[70],cnt;//b是从小到大每一个质因子，inv是对应的逆元

int ksm(int a,int b)
{
    int res = 1;
    while(b)
    {
        if(b&1) res = 1ll*res*a%mod;
        a = 1ll*a*a%mod;
        b>>=1;  
    }
    return res;
}

bool is_prime(int x)
{
    if(x<=1) return 0;
    for(int i=2;i<=x/i;i++)
        if(x%i==0) return 0;
    return 1;
}

void push(Node &u,Node l,Node r)
{
    u.sum = 1ll*l.sum*r.sum%mod;
    u.st = l.st|r.st;
}

void pushup(int u)
{
    push(tr[u],tr[u<<1],tr[u<<1|1]);
}

void build(int u,int l,int r)
{
    if(l==r)
    {
        tr[u] = {l,r,a[l],1};
        for(int i=0;i<cnt;i++) 
            if(a[l]%b[i]==0)
                tr[u].st |= 1ll<<i;//记得st是个ll类型，因此1要开ll，这样才不会爆掉
        return ;
    }
    tr[u] = {l,r,0,1};
    int mid = l + r >> 1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}

void change_mul(Node &u,int x)
{
    u.sum = 1ll*u.sum*ksm(x,u.r-u.l+1)%mod;
    u.mul = 1ll*u.mul*x%mod;
}

void change_cov(Node &u,LL x)//记住，维护区间积的质因子的懒标记是ll的，这点我当时传的int，错了一发
{
    u.st|=x;
    u.cov|=x;
}

void pushdown(int u)
{
    auto &root = tr[u],&left = tr[u<<1],&right = tr[u<<1|1];
    if(root.mul!=1)
    {
        change_mul(left,root.mul);
        change_mul(right,root.mul);
        root.mul = 1;
    }
    if(root.cov)
    {
        change_cov(left,root.cov);
        change_cov(right,root.cov);
        root.cov = 0;
    }
}

void modify(int u,int l,int r,int x)
{
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        tr[u].sum = 1ll*tr[u].sum*ksm(x,tr[u].r - tr[u].l + 1)%mod;
        tr[u].mul = 1ll*tr[u].mul*x%mod;
        for(int i=0;i<cnt;i++)
            if(x%b[i]==0)
            {
                tr[u].st |= 1ll<<i;
                tr[u].cov |= 1ll<<i;
            }
        return ;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(l<=mid) modify(u<<1,l,r,x);
    if(r>mid) modify(u<<1|1,l,r,x);
    pushup(u);
}

Node query(int u,int l,int r)
{
    if(l<=tr[u].l&&tr[u].r<=r) return tr[u];
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(l>mid) return query(u<<1|1,l,r);
    else if(r<=mid) return query(u<<1,l,r);
    else 
    {
        Node res;
        push(res,query(u<<1,l,r),query(u<<1|1,l,r));
        return res;
    }
}

int main()
{
    ios;
    cin>>n>>q;
    for(int i=2;i<=300;i++)
    {
        if(is_prime(i))
        {
            b[cnt] = i;
            inv[cnt] = ksm(i,mod-2);
            cnt++;
        }
    }
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(q--)
    {
        string op;
        int l,r,x;cin>>op>>l>>r;
        if(op[0]=='T')
        {
            int ans = 1;
            auto t = query(1,l,r);
            ans = t.sum;
            for(int i=0;i<cnt;i++)
                if(t.st>>i&1)
                {
                    ans = 1ll*ans*(b[i]-1)%mod;
                    ans = 1ll*ans*inv[i]%mod;
                }
            cout<<ans<<'\n';
        }
        else 
        {
            cin>>x;if(x==1) continue;
            modify(1,l,r,x);
        }
    }
    return 0;
}