CF594D REQ

标签：int res 质数 REQ add CF594D query mod

CF594D REQ

题目大意

给定序列\(a_1,a_2,a_3,...,a_n\)，有\(q\)个询问，每次给定\(l,r\)，询问\(\varphi\left(\prod\limits_{i=l}^ra_i\right)\)。对 $ 10^{9}+7 $ 取模。

\(n,q<=2*10^5,a_i<=10^6\).

分析

比较早期的CF的数据结构题。层层buff叠加下，这题显然不会太难。

我们来简单分析一下。首先看到只有询问，那刻在DNA里的，就要想离线操作。

我们考虑计算\(\phi(\sum_{i=l}^{r}a_i)\)，等于计算

\[\prod_{i=l}^{r}a_i\prod_{p_j| a_i(i\in(l,r)，且p_j为质数)}\frac{p_i-1}{p_i} \]

我们最大的问题时，如何不重复的计算区间内的每个质数，第二次DNA一动，去重又是离线的经典操作。

我们维护树状数组。

我们对区间右端点进行排序，每次扫到一个点i时，将该点的值，以及其所有的质数所对应的贡献加入树状数组，总的来说就是，\(add(i,a_i),add(i,p_j-1),add(i,p_j^{-1})(p_j | a_i且是质数)\)。

如何去重呢？我们只需要记录当前位置加的质数上次出现的位置的0贡献清空即可保证去重。我们维护一个数组pre[x]表示x这个数字上次出现的位置。

还有一个小问题，对于每一个位置，如果我们每次扫到之后再进行求所有的质数，这时间复杂度为\(O(n\sqrt{n})\)。因此我们利用积性函数的性质，O(n)求出。具体实现可以看代码。

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;
typedef pair<int,int> PII;
const int N = 2e5 + 10,M = 1e6 + 10,mod = 1e9 + 7;

struct Node
{
    int l,r,id;
    bool operator<(const Node& W) const 
    {
        return r<W.r;
    }
};

int tr[N];
vector<int> fact[M];
bool st[M];
int primes[M],cnt;
int a[N],ans[N],pre[M],inv[M];
int n,q;

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;
}

void init()
{
    fact[1].push_back(1);st[1] = 1;
    for(int i=2;i<M;i++)
    {
        if(!st[i]) 
        {
            fact[i].push_back(i);
            primes[++cnt] = i;
            inv[i] = ksm(i,mod-2);
            inv[i-1] = ksm(i-1,mod-2);
        }
        for(int j=1;1ll*i*primes[j]<M;j++)
        {
            st[primes[j]*i] = 1;
            fact[primes[j]*i] = fact[i];
            if(i%primes[j]==0) break;
            fact[primes[j]*i].push_back(primes[j]);
        }
    }
}

void add(int x,int c)
{
    while(x<=n)
    {
        tr[x] = 1ll*tr[x]*c%mod;
        x += x & -x;
    }
}

int sum(int x)
{
    int res = 1;
    while(x)
    {
        res = 1ll*res*tr[x]%mod;
        x -= x & -x;
    }
    return res;
}

int main()
{
    ios;
    init();
    cin>>n;
    for(int i=1;i<=n;i++) tr[i] = 1;
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>q;
    vector<Node> query;
    for(int i=0;i<q;i++) 
    {
        int l,r;cin>>l>>r;
        query.push_back({l,r,i});
    }
    sort(query.begin(),query.end());
    int now = 0;
    for(int i=0;i<q;i++)
    {
        int l = query[i].l,r = query[i].r,id = query[i].id;
        while(now<r)
        {
            now++;
            if(a[now]==1) continue;
            add(now,a[now]);
            for(auto x:fact[a[now]])
            {
                if(pre[x]) add(pre[x],inv[x-1]),add(pre[x],x);
                pre[x] = now;
                add(now,x-1),add(now,inv[x]);
            }
        }
        if(l!=1) ans[id] = 1ll*sum(r)*ksm(sum(l-1),mod-2)%mod;
        else ans[id] = sum(r);
    }
    for(int i=0;i<q;i++) cout<<ans[i]<<'\n';
    return 0;
}

标签：int,res,质数,REQ,add,CF594D,query,mod
From： https://www.cnblogs.com/aitejiu/p/16705490.html