Link
设个阈值\(s\)。
对于\(\le s\)的模数，插入时暴力更新。
对于\(>s\)的模数，把插入的数搞到一个set里面，每次查询\(\bmod x\)的最小值时就枚举\(x\)的倍数，lower_bound一下取个\(\min\)就好了。
显然当\(s=\sqrt{n\log n}\)时取到最优复杂度\(O(n\sqrt{n\log n})\)。
#pragma GCC optimize(3)
#include<set>
#include<cstdio>
#include<cctype>
#include<cstring>
using std::set;
namespace IO
{
char ibuf[(1<<21)+1],obuf[(1<<21)+1],st[11],*iS,*iT,*oS=obuf,*oT=obuf+(1<<21);
char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}
void Flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}
void Put(char x){*oS++=x;if(oS==oT)Flush();}
char fetch(){char c=Get();while(!isupper(c))c=Get();return c;}
int read(){int x=0,c=Get();while(!isdigit(c))c=Get();while(isdigit(c))x=x*10+c-48,c=Get();return x;}
void write(int x){int top=0;if(!x)Put('0');while(x)st[++top]=(x%10)+48,x/=10;while(top)Put(st[top--]);Put('\n');}
}using namespace IO;
int min(int a,int b){return a<b? a:b;}
int mn[1507];set<int>s;
int main()
{
int n=read(),B=1500;
s.insert(1000000),memset(mn+1,0x3f,B<<2);
for(int i=1,x;i<=n;++i)
if(fetch()=='A')
{
s.insert(x=read());
for(int i=1;i<=B;++i) mn[i]=min(mn[i],x%i);
}
else
if((x=read())<=B) write(mn[x]);
else
{
int ans=1<<20,t;
for(int i=0;i<=300000;i+=x) if((t=*s.lower_bound(i))<=300000) ans=min(ans,t%x);
write(ans);
}
return Flush(),0;
}原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12210436.html