Loj 2142 相逢是问候

Posted on | Views:

拓展欧拉定理 + 线段树.

拓展欧拉定理:当 $x>\varphi(P)$ 时,有 $a^x\equiv a^{x\bmod \varphi(P)+\varphi(P)} \pmod P$ .

那么只需要对每个位置维护出 $a\bmod P,a\bmod \varphi(P),a\bmod \varphi(\varphi(P)),\dots$ ,就可以实现单点修改.

每次把 $P$ 变成 $\varphi(P)$ ,最多变 $O(\log P)$ 次就会变成 $1$ ,所以每个位置只用维护 $k=O(\log P)$ 个值.

当一个数被操作了 $k$ 次后,就出现了 $\bmod 1$ 的情况,由于可以依次递推出每一项的值,所以再修改,它的值也不会变.

用线段树来实现修改操作,修改一个区间时,若区间内所有数都不变时,直接返回,否则继续向下暴力递归.

每个位置最多被修改 $O(\log P)$ 次,每次修改需要修改 $O(\log P)$ 个值,每修改一个值需要 $O(\log P)$ 算一次快速幂.

所有快速幂的底数都是 $c$ ,而指数不超过 $10^8$ ,所以可以对每种模数预处理出 $c^i,c^{i\times 10^4}$ 的值,快速幂就变成 $O(1)$ 了.

时间复杂度 $O(n\log^2 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
147
148
149
150
151
152
153
154
155
156
157
158
//%std
#include<bits/stdc++.h>
#define endl '\n'
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;
}
int add(int a,int b,int P)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
int mul(int a,int b,int P)
{
	return 1LL * a * b % P;
}
const int MAXN=5e4+10,K=30;
int phi(int x)
{
	int res=x;
	for(int i=2;i*i<=x;++i)
		if(x%i==0)
		{
			while(x%i==0)
				x/=i;
			res/=i,res*=(i-1);
		}
	if(x>1)
		res/=x,res*=(x-1);
	return res;
}
int n,m,k,c,a[MAXN],mod[K],f[MAXN][K];
struct node
{
	int sum,cnt,key;
}Tree[MAXN<<2];
#define root Tree[o]
#define lson Tree[o<<1]
#define rson Tree[o<<1|1]
void pushup(int o)
{
	root.sum=add(lson.sum,rson.sum,mod[0]);
	root.key=lson.key+rson.key;
}
void BuildTree(int o,int l,int r)
{
	if(l==r)
	{
		root.sum=a[l];
		root.cnt=0;
		root.key=1;
		return;
	}
	int mid=(l+r)>>1;
	BuildTree(o<<1,l,mid);
	BuildTree(o<<1|1,mid+1,r);
	pushup(o);
}
void upd(int o,int l,int r,int L,int R)
{
	if(L<=l && r<=R && !root.key)
		return;
	if(l==r)
	{
		++root.cnt;
		if(root.cnt==k)
			root.key=0;
		root.sum=f[l][root.cnt];
		return;
	}
	int mid=(l+r)>>1;
	if(L<=mid)
		upd(o<<1,l,mid,L,R);
	if(R>mid)
		upd(o<<1|1,mid+1,r,L,R);
	pushup(o);
}
int query(int o,int l,int r,int L,int R)
{
	if(L<=l && r<=R)
		return root.sum;
	int mid=(l+r)>>1;
	int res=0;
	if(L<=mid)
		res=add(res,query(o<<1,l,mid,L,R),mod[0]);
	if(R>mid)
		res=add(res,query(o<<1|1,mid+1,r,L,R),mod[0]);
	return res;
}
int pw1[MAXN][K],pw0[MAXN][K];
int Pow(int x,int d)
{
	return mul(pw1[x/10000][d],pw0[x%10000][d],mod[d]);
}
int calc(int x,int num,int d)
{
	if(!num)
		return x%mod[d];
	int t=calc(x,num-1,d+1);
	if(log(1.0*mod[d+1]/x)/log(1.0*c)<num)
		t+=mod[d+1];
	return Pow(t,d);
}
int main()
{
	n=read(),m=read(),mod[0]=read(),c=read();
	k=0;
	while(mod[k]>1)
	{
		++k;
		mod[k]=phi(mod[k-1]);
	}
	mod[++k]=1;
	for(int d=0;d<=k;++d)
	{
		pw0[0][d]=1;
		for(int i=1;i<=10000;++i)
			pw0[i][d]=mul(pw0[i-1][d],c,mod[d]);
		pw1[0][d]=1;
		int pc=pw0[10000][d];
		for(int i=1;i<=10000;++i)
			pw1[i][d]=mul(pw1[i-1][d],pc,mod[d]);
	}
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
		if(!a[i])
		{
			f[i][1]=1;
			for(int j=2;j<=k;++j)
				f[i][j]=calc(1,j-1,0);
		}
		else
		{
			for(int j=1;j<=k;++j)
				f[i][j]=calc(a[i],j,0);
		}
	}
	BuildTree(1,1,n);
	for(int i=1;i<=m;++i)
	{
		int op=read(),L=read(),R=read();
		if(!op)
			upd(1,1,n,L,R);
		else
			printf("%d\n",query(1,1,n,L,R));
	}
	return 0;
}