链接：CodeForces - 482D Kuro and GCD and XOR and SUM

题意：

给一个空的集合$a$a，共有$q\;(2\le q\le 10^5)$q(2≤q≤105)次操作，分为以下$2$2种操作

• $1\;u_i$1ui​：将$u_i$ui​加入到集合$a$a中$\;(1\le u_i\le 10^5)$(1≤ui​≤105)
• $2\;x_i\;k_i\;s_i$2xi​ki​si​：在集合$a$a中找到一个数$v$v，满足$k_i|\gcd(x_i,v),\;x_i+v\le s_i$ki​∣gcd(xi​,v),xi​+v≤si​ 且 $x_i\oplus v$xi​⊕v最大，并输出$v$v，若找不到，则输出$-1\;(1\le x_i,k_i,s_i\le10^5)$−1(1≤xi​,ki​,si​≤105)

---

分析：

首先第一个条件$k_i|\gcd(x_i,v)$ki​∣gcd(xi​,v)，也就是要求满足$k_i|x_i$ki​∣xi​且$k_i|v$ki​∣v，所以若不满足$k_i|x_i$ki​∣xi​，可以直接输出$-1$−1；

后两个条件：$x_i+v\le s_i$xi​+v≤si​ 且 $x_i\oplus v$xi​⊕v最大，可以在字典树上进行查找，为保证$x_i+v\le s_i$xi​+v≤si​（即$v\le s_i-x_i$v≤si​−xi​）,可以再 设置一个变量$min\_val[u]$min_val[u]，表示以$u$u为根结点的子树内存储的最大值；

这样每次查询 即要尽可能与$x_i$xi​异或最大，还要保证对应子树的$min\_val[v]\le s_i-x_i$min_val[v]≤si​−xi​；

其次，为满足$k_i|v$ki​∣v，可以 对每一个$k_i$ki​值建一个01字典树（存储所有$k_i$ki​的倍数，即能被$k_i$ki​整除的数），对于新输入的$u_i$ui​，要把 $u_i$ui​插入到其所有因数对应的树中，找到所有因数的时间只需要$O(\sqrt {u_i})$O(ui​​)。

---

以下代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1e5+50;
const int INF=0x3f3f3f3f;
const int max_base=20;
int ch[maxn*200][2],val[maxn*200],min_val[maxn*200],tot;
struct bit_tire
{
    int root;
    void init()
    {
        ch[tot][0]=ch[tot][1]=0;
        val[tot]=0;
        min_val[tot]=INF;
        root=tot++;
    }
    void insert(int x)
    {
        int u=root;
        for(int i=max_base;i>=0;i--)
        {
            min_val[u]=min(x,min_val[u]);
            int c=(x>>i)&1;
            if(!ch[u][c])
            {
                ch[tot][0]=ch[tot][1]=0;
                val[tot]=0;
                min_val[tot]=INF;
                ch[u][c]=tot++;
            }
            u=ch[u][c];
        }
        min_val[u]=val[u]=x;
    }
    int query_max(int x,int y)   //查询该tire小于等于y的与x异或最大值
    {
        int u=root;
        for(int i=max_base;i>=0;i--)
        {
            int c=(x>>i)&1;
            if(ch[u][c^1]&&min_val[ch[u][c^1]]<=y)
                u=ch[u][c^1];
            else if(ch[u][c]&&min_val[ch[u][c]]<=y)
                u=ch[u][c];
            else
                return -1;
        }
        return val[u];
    }
}t[maxn];
void init()
{
    tot=1;
    for(int i=1;i<maxn;i++)
        t[i].init();
}
int main()
{
    init();
    int q,op,u,x,k,s;
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d",&u);
            int k=(int)round(sqrt(u));
            for(int i=1;i<=k;i++)
            {
                if(u%i==0)
                {
                    t[i].insert(u);
                    t[u/i].insert(u);
                }
            }
        }
        else
        {
            scanf("%d %d %d",&x,&k,&s);
            if(x%k!=0)
                printf("-1\n");
            else
                printf("%d\n",t[k].query_max(x,s-x));
        }
    }
    return 0;
}