Codeforces Round #482 (Div. 2) D. Kuro and GCD and XOR and SUM(数学+01字典树)(好题)
程序员文章站
2023-12-26 12:41:45
...
题目链接
题意:有n个操作,操作1代表往集合里面加入一个数字x,操作2会给出三个数字x,k,s,然后对于每一个2操作,题目有一个询问,要求从集合中找一个数vv满足下面的条件:
gcd(x,v)%k==0
x+v≤s
使x⊕v的值最大
思路:对于第一个条件我们可以建1e5棵字典树,第i棵字典撒插的就是所有的i的倍数,因为v肯定是k的倍数,所以我们最后查询的时候就在第k棵字典树上查询。那么第二个和第三个条件的话只要在01字典树求异或的模板加个判断大小的条件就行了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+50;
int tree[maxn*400][2],sum[maxn*400],pos[maxn],cnt=0;
vector<int>g[maxn];
void insert(int id,int x)
{
int u=pos[id];
for(int i=31;i>=0;--i)
{
int t=(((1LL<<i)&x)?1:0);
if(!tree[u][t]) tree[u][t]=++cnt,sum[tree[u][t]]=x;
else sum[tree[u][t]]=min(sum[tree[u][t]],x);
u=tree[u][t];
}
sum[u]=min(sum[u],x);
}
int query(int x,int id,int s)
{
if(x%id!=0) return -1;
int u=pos[id];
for(int i=31;i>=0;--i)
{
int t=(((1LL<<i)&x)?1:0);
if(tree[u][t^1]&&sum[tree[u][t^1]]<=s-x) u=tree[u][t^1];
else if(sum[tree[u][t]]<=s-x) u=tree[u][t];
else return -1;
}
return sum[u];
}
int main()
{
int q,op,x,k,s;
memset(sum,0x3f3f3f3f,sizeof(sum));
for(int i=1;i<maxn;++i)
{
pos[i]=++cnt;
for(int j=i;j<maxn;j+=i)
g[j].push_back(i);
}
scanf("%d",&q);
while(q--)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d",&x);
for(int to:g[x]) insert(to,x);
}
else scanf("%d %d %d",&x,&k,&s),printf("%d\n",query(x,k,s));
}
}