bzoj 4026 dC Loves Number Theory

Posted on | Views:

主席树.

区间 $[L,R]$ 的答案可以表示成 $\prod_{i=L}^R A_i\cdot \prod \frac {p_i-1}{p_i}$ .

前者容易维护,后者就是所有在 $[L,R]$ 区间内出现过的质数的贡献,做法比较经典.

从前往后依次加入元素,加入 $A_i$ 时,枚举 $A_i$ 的所有质因子 $p$ ,在第 $i$ 棵线段树中给位置 $i$ 乘上 $\frac {i-1} i$ .

若 $p$ 在之前出现过,且最后一个出现的位置是 $lst$ ,则还要在第 $i$ 棵线段树中给位置 $lst$ 乘上 $\frac i {i-1}$ ,即消除贡献.

询问时,后面那个 $\prod \frac {p_i-1}{p_i}$ 就是在第 $R$ 棵线段树中询问区间 $[L,R]$ 的连乘积.

用主席树来维护,时间复杂度 $O(P+n\log n\log P)$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=1e6+777;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
int inv[P+10],pcnt=0,prime[P+10],ism[P+10],minp[P+10];
void init_pr()
{
	inv[1]=1;
	for(int i=2;i<P;++i)
		inv[i]=mul(P-P/i,inv[P%i]);
	ism[1]=1;
	for(int i=2;i<P;++i)
	{
		if(!ism[i])
		{
			prime[++pcnt]=i;
			minp[i]=i;
		}
		for(int j=1;j<=pcnt && i*prime[j]<P;++j)
		{
			int num=i*prime[j];
			ism[num]=1;
			minp[num]=prime[j];
			if(i%prime[j]==0)
				break;
		}
	}
}
const int MAXN=5e4+10;
int lastans=0;
int n,m,preprod[MAXN],a[MAXN],rt[MAXN];
struct PreSegtree
{
	int idx;
	PreSegtree(){idx=0;}
	struct node
	{
		int ls,rs;
		int prod;
		node(){ls=rs=0;prod=1;}		
	}Tree[MAXN*100];
#define root Tree[o]
	void upd(int &o,int lst,int l,int r,int pos,int c)
	{
		o=++idx;
		root=Tree[lst];
		root.prod=mul(root.prod,c);
		if(l==r)
			return;
		int mid=(l+r)>>1;
		if(pos<=mid)
			upd(root.ls,Tree[lst].ls,l,mid,pos,c);
		else
			upd(root.rs,Tree[lst].rs,mid+1,r,pos,c);
	}
	void query(int o,int l,int r,int L,int R,int &res)
	{
		if(L<=l && r<=R)
			return (void)(res=mul(res,root.prod));
		int mid=(l+r)>>1;
		if(L<=mid)
			query(root.ls,l,mid,L,R,res);
		if(R>mid)
			query(root.rs,mid+1,r,L,R,res);
	}
}T;
int lst[P+10];
void init_seg()
{
	for(int i=1;i<=n;++i)
	{
		int x=a[i];
		int lsp=rt[i-1],cur;
		while(x!=1)
		{
			int p=minp[x],cnt=0;
			if(lst[p])
			{
				T.upd(cur,lsp,1,n,lst[p],mul(p,inv[p-1]));
				lsp=cur;
			}
			T.upd(cur,lsp,1,n,i,mul(p-1,inv[p]));
			lsp=cur;
			lst[p]=i;
			while(x%p==0)
				x/=p;
		}
		rt[i]=cur;
	}
}
int solve(int L,int R)
{
	lastans=mul(preprod[R],inv[preprod[L-1]]);
	T.query(rt[R],1,n,L,R,lastans);
}
int main()
{
	init_pr();
	n=read(),m=read();
	preprod[0]=1;
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
		preprod[i]=mul(preprod[i-1],a[i]);
	}
	init_seg();
	for(int i=1;i<=m;++i)
	{
		int L=read()^lastans,R=read()^lastans;
		solve(L,R);
		printf("%d\n",lastans);
	}
	return 0;
}