526互联

CF979D Kuro and GCD and XOR and SUM

发布时间 2023-08-27 07:52:15作者: -白简-

题目大意

初始有一个空的集合，和 \(Q\) 个操作。对于每个操作，有两种类型，分别用如下的两种形式表示：

1 u：加入 \(u\) 到集合
2 x k s：求一个最大的 \(v\)，使得:

  1. \(v+x \leq s\)
  2. \(k \mid \gcd(v,x)\)
  3. \(x \oplus v\) 最大（其中 \(\oplus\) 表示按位异或，对应 C++ 中的 ^ 运算符）

如果找不到满足条件的 \(v\)，输出 \(-1\)。

思路

考虑第二个限制，我们可以转化为 \(k \mid x \land k \mid v\)，那么 \(x\) 和 \(v\) 都是 \(k\) 的倍数，我们可以预处理加入集合的数 \(u\)，把它加入所有它因数的集合里。

这样在后面查找 \(v\) 就直接在 \(k\) 的集合中查找就能够保证满足第二个条件。

对于查询操作，直接找到小于等于 \(s-x\) 的数，然后在集合中从大到小遍历。

知道，两个数异或值最大就是两个数的值相加，如果当前记录的最大异或值 Max 已经大于遍历到的 x + v，后面的部分肯定不会再对答案产生贡献了，可以直接退出循环。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 100500;

int n;
int opt,u,x,k,s;

set<int> S[N];
// S[i] 中的任意数 x 满足 i | x 
// 即存的是 i 的倍数 
// 用于第二个条件 

long long ans,Max;

int main() {
    cin >> n;

    for(int i = 1;i <= n; i++) {
        cin >> opt;
        if(opt == 1) {
            cin >> u;
            for(int i = 1;i <= floor(sqrt(u)); i++) {
                if(u % i == 0) {
                    S[i].insert(u);
                    S[u / i].insert(u);
                }// 记录的是其倍数 
            }
        }
        else {
            cin >> x >> k >> s;
            
            ans = -1;
            Max = -1;

            if(x % k != 0) {
                cout << "-1\n";
                continue;
            }

            set<int>::iterator it = S[k].upper_bound(s - x);
            // 找到大于 v 的最小的数 
            if(it == S[k].begin() || S[k].empty()) {
                cout << "-1\n";
                continue;
            }

            it --;
            // 现在的 it 指向的是满足第一个条件和第二个条件的最大的数

            while(it != S[k].begin()) {
                int v = *it;

                if(Max > x + v) 
                    break;
                // 异或最大值就是 x + v 
                // Max 已经超过 x + v 肯定不能更新答案 
                
                if(Max < (v ^ x)) {
                    Max = v ^ x;
                    ans = v;
                }

                it --;
            }

            if((*it ^ x) > Max)
                ans = *it;
            
            cout << ans << "\n";
        }
    }
    return 0;
}