CodeForces 979 D Kuro and GCD and XOR and SUM

题意：给你一个空数组。然后有2个操作， 1是往这个数组里面插入某个值， 2.给你一个x, k, s。要求在数组中找到一个v，使得k|gcd(x,v) （即gcd(x,v)是k的倍数，v+x <= k, x ^ v的值最大。

题解：XOR亦或问题是经典的题目，一般都是用01字典树去处理。然后需要满足条件1，所以我们可以对于每一个点建立一个字典树，每次添加数的时候都往这个数的因子添加这个值，这样我们直接访问对应的k就可以找到答案了。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const LL mod = 1e9+;

 const int N = 1e5+;

 vector<int> son[N];

 struct Node{

     int Min;

     Node * p[];

     Node(){

         Min = INF;

         p[] = p[] = nullptr;

     }

 }*rt[N];

 bool vis[N];

 void init(){

     for(int i = ; i < N; i++){

         rt[i] = new Node();

         for(int j = i; j < N; j+=i){

             son[j].pb(i);

         }

     }

 }

 void Add(int k, int u){

     Node *tmp = rt[k];

     tmp -> Min = min(tmp -> Min, u);

     for(int i = ; i >= ; i--){

         int id = u>>i & ;

         if(tmp -> p[id] == nullptr)

             tmp -> p[id] = new Node();

         tmp = tmp -> p[id];

         tmp -> Min = min(tmp -> Min, u);

     }

 }

 int Query(int x, int k, int s){

     Node *tmp = rt[k];

     if(x%k !=  || tmp->Min+x > s)

         return -;

     int ret = ;

     for(int i = ; i >= ; i--){

         int id = x >> i & ;

         if(tmp -> p[id^] != nullptr && tmp -> p[id^] -> Min + x <= s){

             tmp = tmp -> p[id^];

             ret += (id^) << i;

         }

         else {

             tmp = tmp -> p[id];

             ret += id << i;

         }

     }

     return ret;

 }

 int main(){

     ///Fopen;

     init();

     int q, t, u, x, s, k;

     scanf("%d", &q);

     while(q--){

         scanf("%d", &t);

         if(t == ){

             scanf("%d", &u);

             if(!vis[u]){

                 vis[u] = ;

                 for(int k : son[u]){

                     Add(k, u);

                 }

             }

         }

         else{

             scanf("%d%d%d", &x, &k, &s);

             printf("%d\n", Query(x,k,s));

         }

     }

     return ;

 }

巴特西

CodeForces 979 D Kuro and GCD and XOR and SUM

最新文章

热门文章