C++(g++ 7.5.0) 解法, 执行用时: 2438ms, 内存消耗: 51012K, 提交时间: 2022-09-02 20:41:45

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int ksm(ll a,ll p,ll M){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}
int i,j,k,n,m,t,a[500500],res;
set<int> s[500500];

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	
	cin>>n>>t;
	for(i=1;i<=n;i++){
		cin>>a[i];
		s[a[i]].insert(i);
	}
	while(t--){
		int op,l,r,p;
		cin>>op>>l>>r;
		if(op==1){
			s[a[l]].erase(l);
			a[l]=r;
			s[a[l]].insert(l);
		}
		else{
			cin>>p;res=0;
			for(i=p-1;i>=1;i--){
				int t=ksm(i,p-2,p);
				for(j=t;j<=n;j+=p){
					if(s[j].empty())continue;
					auto it=s[j].lower_bound(l);
					if(it!=s[j].end()&&(*it)<=r){
						res=i;goto aaa;
					}
				}
			}
			aaa:;
			cout<<res<<'\n';
		}
	}
}

C++(clang++ 11.0.1) 解法, 执行用时: 2500ms, 内存消耗: 50976K, 提交时间: 2022-09-02 21:23:46

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=5e5+7;
int n,m,a[M],op,x,y,p,nw;
set<int> se[M];
int ksm(ll a,int b,int Mod){
	ll ans=1;
	while(b){
		if(b&1) ans=ans*a%Mod;
		a=a*a%Mod,b>>=1;
	}
	return (int)ans;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),
		se[a[i]].insert(i);
	while(m--){
		scanf("%d%d%d",&op,&x,&y);
		if(op==1)
			se[a[x]].erase(x),a[x]=y,
			se[a[x]].insert(x);
		else{
			scanf("%d",&p);
			for(int i=p-1;i>=1;i--){
				nw=ksm(i,p-2,p);
				for(int j=nw;j<=n;j+=p)
					for(auto k:se[j])
						if(x<=k && k<=y){
							printf("%d\n",i);
							goto fin;
						}
			}
			puts("0");
			fin:;
		}
	}
	return 0;
}