题目大意
初始有一个空的集合,和 \(Q\) 个操作。对于每个操作,有两种类型,分别用如下的两种形式表示:
1 u
:加入 \(u\) 到集合
2 x k s
:求一个最大的 \(v\),使得:
- \(v+x \leq s\)
- \(k \mid \gcd(v,x)\)
- \(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;
}
标签:Kuro,XOR,cout,int,Max,CF979D,异或,ans,集合
From: https://www.cnblogs.com/baijian0212/p/CF979D.html