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