BZOJ4026: 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

考虑phi函数的定义

phi(n)=n*∏(pi-1)/pi。

所以我们对于每个询问，计算出询问区间内有多少不同的素数就行啦。

这难道不是一个经典问题吗？在线回答区间不同数的个数。

设f[i]表示第i个素数上一次出现的位置，那么我们用函数式线段树计算一下区间内f[i]<L-1的数的(pi-1)/pi之积即可。

一个正整数最多有logn个质因子，而每插入一个质因子是logn的，所以时间复杂度为O(nlog^2n)-O(logn)。

另外掌握了O(n)求1到n逆元的姿势。

#include<cstdio>

#include<cctype>

#include<queue>

#include<cmath>

#include<cstring>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define ren for(int i=first[x];i;i=next[i])

using namespace std;

const int BufferSize=<<;

char buffer[BufferSize],*head,*tail;

inline char Getchar() {

    if(head==tail) {

        int l=fread(buffer,,BufferSize,stdin);

        tail=(head=buffer)+l;

    }

    return *head++;

}

inline int read() {

    int x=,f=;char c=Getchar();

    for(;!isdigit(c);c=Getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=Getchar()) x=x*+c-'';

    return x*f;

}

typedef long long ll;

const int maxn=;

const int mod=;

const int maxnode=;

int n,m,cnt,A[maxn],vis[mod+],first[mod+],pri[mod],next[mod*],to[mod*],e;

ll inv[mod+],S[maxn],sumv[maxnode],lastans;

void init() {

    inv[]=inv[]=;

    rep(i,,mod) inv[i]=((mod-mod/i)*inv[mod%i]+mod)%mod;

    rep(i,,) if(!vis[i]) {

        pri[++cnt]=i;

        for(int j=i;j<=;j+=i) {

            vis[j]=;

            to[++e]=cnt;next[e]=first[j];first[j]=e;

        }

    }

}

int root[maxn],last[mod+],ls[maxnode],rs[maxnode],ToT;

void update(int& y,int x,int l,int r,int p,ll v) {

    sumv[y=++ToT]=((x?sumv[x]:)*v)%mod;if(l==r) return;

    int mid=l+r>>;ls[y]=ls[x];rs[y]=rs[x];

    if(p<=mid) update(ls[y],ls[x],l,mid,p,v);

    else update(rs[y],rs[x],mid+,r,p,v);

}

ll query(int y,int l,int r,int pos) {

    if(l==r) return y?sumv[y]:;

    int mid=l+r>>;

    if(pos<=mid) return query(ls[y],l,mid,pos);

    return ((ls[y]?sumv[ls[y]]:)*query(rs[y],mid+,r,pos))%mod;

}

int main() {

    init();S[]=;

    n=read();m=read();

    rep(i,,n) A[i]=read(),S[i]=(S[i-]*A[i])%mod;

    rep(x,,n) {

        root[x]=root[x-];

        for(int i=first[A[x]];i;i=next[i]) update(root[x],root[x],,n,last[to[i]],(pri[to[i]]-)*inv[pri[to[i]]]%mod),last[to[i]]=x;

    }

    while(m--) {

        int l=read()^lastans,r=read()^lastans;

        lastans=(S[r]*inv[S[l-]])%mod;

        (lastans*=inv[query(root[l-],,n,l-)]*query(root[r],,n,l-))%=mod;

        printf("%lld\n",lastans);

    }

    return ;

}

巴特西