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
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
我们处理出前缀积，问题就转化为求区间所有的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
*/