做法是这样的，对于Y<=block，直接暴力出解
对于Y>=block 枚举每一个Y的每一个倍数，然后找到这个倍数在当前块的后继更新答案。
但是有些时候，当前块没有Y的后继，那么就要去下一个块找，方便起见，mn[i]记录记录第i+1块~第block块最小值
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; const int block=547; int st[310000]; int bl[310000];//暴力把 Y<=block的答案硬算出来 int c[310000],mn[310000];//c[i]记录i同一个块的后继 mn[i]记录第i+1块~第block块最小值 void ins(int x) { for(int i=1;i<=block;i++)bl[i]=min(bl[i],x%i); for(int i=x;i>=0;i--) { if(st[i]!=st[i+1]&&i!=x)break; c[i]=min(c[i],x); } for(int i=st[x]-1;i>=1;i--)mn[i]=min(mn[i],x); } int query(int x) { if(x<=block)return bl[x]; int ret=(1<<30); for(int i=0;i<=300000;i+=x) ret=min(ret,min(mn[st[i]],c[i])-i); return ret; } char ss[10]; int main() { memset(bl,63,sizeof(bl)); memset(mn,63,sizeof(mn)); memset(c,63,sizeof(c)); st[0]=1;for(int i=1;i<=300000;i++)st[i]=(i-1)/block+1; int n,x; scanf("%d",&n); while(n--) { scanf("%s%d",ss+1,&x); if(ss[1]=='A')ins(x); else printf("%d ",query(x)); } return 0; }