BZOJ_4026_dC Loves Number Theory _主席树+欧拉函数

Description

dC 在秒了BZOJ 上所有的数论题后，感觉萌萌哒，想出了这么一道水题，来拯救日益枯

竭的水题资源。

给定一个长度为 n的正整数序列A，有q次询问，每次询问一段区间内所有元素乘积的

φ（φ(n)代表1~n 中与n互质的数的个数）。由于答案可能很大，所以请对答案 mod 10^6 +

777。（本题强制在线，所有询问操作的l,r都需要 xor上一次询问的答案 lastans，初始时，

lastans = 0）

Input

第一行，两个正整数，N，Q，表示序列的长度和询问的个数。

第二行有N 个正整数，第i个表示Ai.

下面Q行，每行两个正整数，l r，表示询问[l ^ lastans,r ^ lastans]内所有元素乘积的φ

Output

Q行，对于每个询问输出一个整数。

Sample Input

5 10
3 7 10 10 5
3 4
42 44
241 242
14 9
1201 1201
0 6
245 245
7 7
6 1
1203 1203

Sample Output

40
240
12
1200
2
240
4
4
1200
4

HINT

1 <= N <= 50000

1 <= Q <= 100000

1 <= Ai <= 10^6

我们处理出前缀积，问题就转化为求区间所有的p-1/p乘起来。

于是我们对ai含有的质因子p,在i对应的位置乘上p-1/p，在pre[p]的位置乘上p/p-1.

然后查询时找到r处的线段树，查询l到r的区间乘积即可。

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int mod=1000777;

#define N 50050

#define M 1005050

int inv[M],n,m,a[N];

int prime[M],cnt,vis[M],s[N],root[N],tot,mul[N*100],lst[M],ls[N*100],rs[N*100],ans,mx;

void init() {

    int i,j;

    for(i=2;i<=mx;i++) {

        if(!vis[i]) prime[++cnt]=i;

        for(j=1;j<=cnt&&i*prime[j]<=mx;j++) {

            vis[i*prime[j]]=1;

            if(i%prime[j]==0) break;

        }

    }

    inv[1]=1;

    for(i=2;i<mod;i++) inv[i]=ll(mod-(mod/i))*inv[mod%i]%mod;

}

void insert(int l,int r,int v,int c,int &y,int x) {

    y=++tot;

    mul[y]=ll(mul[x])*c%mod;

    if(l==r) return ;

    int mid=(l+r)>>1;

    if(v<=mid) rs[y]=rs[x],insert(l,mid,v,c,ls[y],ls[x]);

    else ls[y]=ls[x],insert(mid+1,r,v,c,rs[y],rs[x]);

}

int query(int l,int r,int x,int y,int p) {

    if(x<=l&&y>=r) return mul[p];

    int mid=(l+r)>>1,re=1;

    if(x<=mid) re=ll(re)*query(l,mid,x,y,ls[p])%mod;

    if(y>mid) re=ll(re)*query(mid+1,r,x,y,rs[p])%mod;

    return re;

}

int main() {

    scanf("%d%d",&n,&m);

    int i,j,x,y;

    mul[0]=1;

    for(i=1;i<=n;i++) scanf("%d",&a[i]),mx=max(mx,a[i]);

    init();

    for(s[0]=1,i=1;i<=n;i++) {

        // scanf("%d",&a[i]);

        // printf("%d:\n",a[i]);

        int tmp=a[i]; root[i]=root[i-1];

        if(a[i]==1) {

            s[i]=s[i-1]; continue;

        }

        for(j=1;j<=cnt&&prime[j]*prime[j]<=tmp;j++) {

            if(tmp%prime[j]==0) {

                // printf(" %d ",prime[j]);

                if(lst[prime[j]]) insert(1,n,lst[prime[j]],ll(prime[j])*inv[prime[j]-1]%mod,root[i],root[i]);

                insert(1,n,i,ll(prime[j]-1)*inv[prime[j]]%mod,root[i],root[i]);

                lst[prime[j]]=i;

                while(tmp%prime[j]==0) tmp/=prime[j];

            }

        }

        if(tmp!=1) {

            if(lst[tmp]) insert(1,n,lst[tmp],ll(tmp)*inv[tmp-1]%mod,root[i],root[i]);

            insert(1,n,i,ll(tmp-1)*inv[tmp]%mod,root[i],root[i]);

            lst[tmp]=i;

        }

        // puts("");

        s[i]=ll(s[i-1])*a[i]%mod;

    }

    // ans=40;

    while(m--) {

        scanf("%d%d",&x,&y);

        x^=ans; y^=ans;

        if(x>y) swap(x,y);

        printf("%d\n",ans=ll(s[y])*inv[s[x-1]]%mod*query(1,n,x,y,root[y])%mod);

    }

}

/*

5 10

3 7 10 10 5

3 4

42 44

241 242

14 9

1201 1201

0 6

245 245

7 7

6 1

1203 1203

*/

巴特西