OI - 相逢是问候(洛谷) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - 相逢是问候(洛谷)

发表于 分类于 Valine：

光速幂套扩展欧拉定理写吐了……

# 题面

> 洛谷 P3747

点击展开/折叠题面

维护一个长度为 $n$ 的数组 $A$，给定 $C,P$，对它进行 $m$ 次操作：

  1. 0 l r表示将 $l$ 到 $r$ 的 $a_i$ 替换为 $C^{a_i}$；
  2. 1 l r求 $l$ 到 $r$ 的和对 $P$ 取模的结果。

# 解析

因为 $P$ 不是质数又要求一个幂对 $P$ 取模的结果，就容易想到欧拉定理；而且 $(C,P)$ 没有保证为 $1$，所以需要扩展欧拉定理。

然后我们看看连续对 $a_i$ 进行两次修改过后会变成什么样：

（那个 $d_i$ 是因为扩展欧拉定理 $C^a$ 如果 $a\ge \varphi(P)$ 就取模过后还要再加上 $\varphi(P)$，但是 $a<\varphi(P)$ 就不能加，所以写成这个样子方便一些）

然后我们发现有一个欧拉函数的嵌套，这样嵌套 $O(\log n)$ 次就会降到 $1$。降到 $1$ 过后就不会继续改变了，注意这里的降到 $1$ 是指嵌套到取模 $\varphi(1)$，而不是说取模到 $\varphi(\varphi(\dots\varphi(P)))=1$，不然的话只取模到 $\varphi(2)=1$ 会出问题。

记 $P$ 在嵌套 $k$ 次欧拉函数过后变成 $1$。然后区间修改时，我们对每个修改次数小于 $k$ 的点做一次暴力修改，即直接嵌套计算该点的幂值，因为 $k$ 为 $O(\log n)$，再套上快速幂的一个 $\log$，一个点修改一次的复杂度就是 $O(\log^2 n)$。

每个点最多修改 $k$ 次，$n$ 个点的总复杂度就是 $O(n\log^3 n)$。看起来有点问题，之后再说。

实现的话就是用线段树，如果当前区间中每个数都修改了超过 $k$ 次，就不进入修改，否则递归进去找修改小于 $k$ 次的数。

具体说说怎么暴力计算嵌套幂。

注意到扩展欧拉定理如果 $C^a$ 的 $a\ge\varphi(P)$ 是要再加 $\varphi(P)$ 的，所以在进行下面计算的时候：

判断 $d_2$ 是否是 $\varphi(P)$ 时，不能用 $C^{a\bmod \varphi(\varphi(p))+d_1}\bmod\varphi(P)$ 来和 $\varphi(P)$ 比较大小，为什么会有这个问题？因为我们写快速幂的时候会用 Pow(a,b,mod) 直接计算出 $C^{a\bmod \varphi(\varphi(p))+d_1}\bmod\varphi(P)$，所以快速幂的时候还要存一下是否已经取模了 $\varphi(P)$，如果取模了就说明了 $C^{a\bmod\varphi(\varphi(P))+d_1}\ge\varphi(P)$。

接下来再看复杂度的问题，可以看到多了一个 $\log$ 而且我们发现一个位置修改 $\log$ 次和每次修改需要嵌套 $\log$ 次免不掉，只能尝试砍一下快速幂。

我们发现快速幂的特点是底数一直都是 $C$……所以网上就有一个称作光速幂的东西。

因为模数不超过 $10^8$，我们令 $T=10^4+10$（反正 $T>10^4$ 就是了），然后把 $C^{x}$ 的 $x$ 拆成 $x_1T+x_2$（$0\le x_2< T$）。我们只需要预处理 $C^{iT}$（$0\le i\le T$） 和 $C^{i}$（$0\le i< T$），然后就可以 $O(1)$ 计算了。

仍然要像快速幂一样记录是否已经取模，用一个 bool 数组储存一下，具体看看代码吧。

# 源代码

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

inline int Ri(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
	return r;
}

#define cs const int &
const int N=5e4+10,M=1e4+10;

int n,m,P,C,nphi;
bool flag;
int num[N],phiP[100];
bool exMk[100][M],exk[100][M];
int poMk[100][M],pok[100][M];

inline int Add(cs a,cs b){return a+b>=P? a+b-P:a+b;}
inline int Sub(cs a,cs b){return a-b<0? a-b+P:a-b;}
inline int Mul(cs a,cs b){return 1ll*a*b%P;}
inline int Pow(int b,int mod){
	flag=exMk[mod][b/M]|exk[mod][b%M];
	if(1ll*poMk[mod][b/M]*pok[mod][b%M]>=phiP[mod]) flag=true;
	return 1ll*poMk[mod][b/M]*pok[mod][b%M]%phiP[mod];
}

int Phi(int x){
	int res=x;
	for(int i=2;1ll*i*i<=x;i++){
		if(x%i==0){
			while(x%i==0) x/=i;
			res=res/i*(i-1);
		}
	}
	if(x>1) res=res/x*(x-1);
	return res;
}

struct SEGTREE{
	int sum[N<<1],mxdep[N<<1];
	#define idx(l,r) (((l)+(r))|((l)!=(r)))
	void PushUp(int le,int ri){
		int mi=(le+ri)>>1;
		sum[idx(le,ri)]=Add(sum[idx(le,mi)],sum[idx(mi+1,ri)]);
		mxdep[idx(le,ri)]=max(mxdep[idx(le,mi)],mxdep[idx(mi+1,ri)]);
	}
	void Build(int le,int ri){
		if(le==ri){
			sum[idx(le,ri)]=num[le];
			mxdep[idx(le,ri)]=nphi;
			return;
		}
		int mi=(le+ri)>>1;
		Build(le,mi),Build(mi+1,ri);
		PushUp(le,ri);
	}
	void Modify(int le,int ri,int Le,int Ri){
		if(mxdep[idx(le,ri)]==1) return;
		if(le==ri){
			int u=idx(le,ri);
			int tmpa=num[le];
			mxdep[u]--;
			flag=(tmpa>=phiP[nphi-mxdep[u]-1]);
			for(int i=nphi-mxdep[u];i>=1;i--){
				if(flag) tmpa=tmpa%phiP[i]+phiP[i];
				tmpa=Pow(tmpa,i-1);
			}
			sum[u]=tmpa;
			return;
		}
		int mi=(le+ri)>>1;
		if(Le<=mi) Modify(le,mi,Le,Ri);
		if(mi<Ri) Modify(mi+1,ri,Le,Ri);
		PushUp(le,ri);
	}
	int Query(int le,int ri,int Le,int Ri){
		if(Le<=le && ri<=Ri) return sum[idx(le,ri)];
		int mi=(le+ri)>>1;
		if(Ri<=mi) return Query(le,mi,Le,Ri);
		if(mi<Le) return Query(mi+1,ri,Le,Ri);
		return Add(Query(le,mi,Le,Ri),Query(mi+1,ri,Le,Ri));
	}
}Se;

void Init(){
	phiP[nphi++]=P;
	while(phiP[nphi-1]>1){
		phiP[nphi]=Phi(phiP[nphi-1]);
		nphi++;
	}
	phiP[nphi++]=1;
	for(int i=0;i<nphi;i++){
		if(phiP[i]==1) exk[i][0]=true,pok[i][0]=0;
		else pok[i][0]=1;
		for(int j=1;j<M;j++){
			exk[i][j]=exk[i][j-1];
			if(1ll*pok[i][j-1]*C>=phiP[i]) exk[i][j]=true;
			pok[i][j]=1ll*pok[i][j-1]*C%phiP[i];
		}
		if(phiP[i]==1) poMk[i][0]=0,exk[i][0]=true;
		else poMk[i][0]=1;
		exMk[i][1]=exk[i][M-1];
		if(1ll*pok[i][M-1]*C>=phiP[i]) exMk[i][1]=true;
		poMk[i][1]=1ll*pok[i][M-1]*C%phiP[i];
		for(int j=2;j<M;j++){
			exMk[i][j]=exMk[i][j-1];
			if(1ll*poMk[i][j-1]*poMk[i][1]>=phiP[i]) exMk[i][j]=true;
			poMk[i][j]=1ll*poMk[i][j-1]*poMk[i][1]%phiP[i];
		}
	}
}
int main(){
	n=Ri(),m=Ri(),P=Ri(),C=Ri();
	Init();
	for(int i=1;i<=n;i++) num[i]=Ri();
	Se.Build(1,n);
	while(m--){
		int cmd=Ri(),l=Ri(),r=Ri();
		if(cmd) printf("%d\n",Se.Query(1,n,l,r)%P);
		else Se.Modify(1,n,l,r);
	}
	return 0;
}

THE END

Thanks for reading!

> Linked 此生如歌-网易云