处理大于 $\sqrt{n}$ 的做法应该与CF1157E做法类似。

尝试自己写了一个，疑似要退化成 $O(n^2)$，主要就是因为模数不固定。

谁来帮帮我啊，不好意思再问尺子姐姐了QAQ。

#include<bits/stdc++.h>
#define int long long
#define N 1000005
#define INF 1e18
using namespace std;
const int M=3e5;
int n,a[N],b[N],blc,ans[N],c[N],fa[N],mx;
char ch[N];
int Find(int x){
	if(b[x]) return x;
	return fa[x]=Find(fa[x]);
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n,blc=sqrt(3e5);
	memset(ans,0x3f,sizeof(ans));
	memset(c,0x3f,sizeof(c));
	for(int i=1;i<=n;i++){
		cin>>ch[i]>>a[i],b[a[i]]++;
		if(ch[i]=='B') continue;
		for(int j=1;j<=blc;j++)
			c[j]=min(c[j],a[i]%j);
	}
	for(int i=0;i<M;i++) fa[i]=i+1;
	for(int i=n;i;i--){
		if(ch[i]=='A') b[a[i]]--;
		else{
			if(a[i]<=blc){
				ans[i]=c[a[i]];
				continue;
			}
			//退化处：累加 cnt 
			fa[a[i]-1]=0,ans[i]=INF; int tmp;
			for(int j=0;j<=M;j+=a[i]){
				tmp=Find(j);
				ans[i]=min(ans[i],tmp-j);
			}
			fa[a[i]-1]=a[i];
		}
	}
	for(int i=1;i<=n;i++){
		if(ch[i]=='B') cout<<ans[i]<<endl;
	}
	return 0;
}