CF1945H GCD is Greater

tags

模拟 优先队列

中文题面

给定长度为 $n(n\ge 4)$ 的序列 $a$ 和整数 $x$，将每个元素划分至 $A$ 集合或 $B$ 集合，要求 $|A|,|B|\ge 2$ 且 $A$ 集合中所有元素的 $\gcd$ 严格大于 $B$ 集合中所有元素的按位与加 $x$，即 gcd ⁡ y ∈ A { y } > AND ⁡ y ∈ B { y } + x \gcd _{y \in A} \{y\} > \operatorname{AND}_{y \in B}\{y\}+x gcdy∈A​{y}>ANDy∈B​{y}+x，给出方案或判断无解。

多测， 1 ≤ ∑ n , ∑ max ⁡ { a i } ≤ 4 ⋅ 1 0 5 1 \le \sum n,\sum \max \{a_i\} \le 4 \cdot 10^5 1≤∑n,∑max{ai​}≤4⋅105

思路

首先我们可以确定的是对于 $gcd$ 我们只选两个数，因为选多了会让 $gcd$ 变小，同时让按位与增大。

枚举每个二进制位：

• 如果全是 $1$，那 按位与 确定是 $1$。
• 如果只有一个 $0$，如果 $\gcd$ 取到了这个 $0$（$n-1$ 种选法）按位与 为 $1$，否则确定是 $0$。
• 如果只有两个 $0$，如果 $\gcd$ 取到了这两个 $0$ 则 按位与 为 $1$，否则确定是 $0$。

上述需要特判的位置对至多只有 $O(n\log n)$ 对，直接判即可。

剩下的情况 按位与 确定。我们需要在被 ban 掉的位置对之外找到 $\gcd$ 最大的一对。

枚举 $\gcd =d$，用调和的复杂度求出元素为 $d$ 的倍数的个数 $x$ 以及被 ban 掉的个数 $y$。如果 $y<C_x^2$，那我们能做到 $\gcd =d$。

然后暴力找即可

代码

#include <iostream>
#define N 400002
using namespace std;
int T,n,m,x,a[N],tmp[N],sump[N],sums[N],vis[N];
bool tag[N];
int gcd(int a,int b)
{if(a%b==0) return b;return gcd(b,a%b);
}
int main()
{cin >> T;while(T--){cin >> n >> x;for(int i=1;i<=n;i++) cin >> a[i];m=0;sump[0]=sums[n+1]=(1<<30)-1;for(int i=1;i<=n;i++) m=max(m,a[i]);for(int i=1;i<=m;i++) vis[i]=0;for(int i=1;i<=n;i++) tag[i]=0;for(int i=1;i<=n;i++) vis[a[i]]++;int ans1=-1,ans2=-1;for(int i=0;(1<<i)<=m;i++){if(ans1!=-1) break;int cnt=0;for(int j=1;j<=n;j++){if(!((1<<i)&a[j])) tmp[++cnt]=j;}if(cnt==1){for(int j=1;j<=n;j++){if(j==tmp[1]) sump[j]=sump[j-1];else sump[j]=sump[j-1]&a[j];}for(int j=n;j>=1;j--){if(j==tmp[1]) sums[j]=sums[j+1];else sums[j]=sums[j+1]&a[j];}for(int j=1;j<=n;j++){if(j==tmp[1]) continue;if(gcd(a[tmp[1]],a[j])>(sump[j-1]&sums[j+1])+x){ans1=tmp[1];ans2=j;break;}}if(!tag[tmp[1]]) tag[tmp[1]]=1,vis[a[tmp[1]]]--;}else if(cnt==2){for(int j=1;j<=n;j++){if(j==tmp[1]) sump[j]=sump[j-1];else sump[j]=sump[j-1]&a[j];}for(int j=n;j>=1;j--){if(j==tmp[1]) sums[j]=sums[j+1];else sums[j]=sums[j+1]&a[j];}for(int j=1;j<=n;j++){if(j==tmp[1]) continue;if(gcd(a[tmp[1]],a[j])>(sump[j-1]&sums[j+1])+x){ans1=tmp[1];ans2=j;break;}}for(int j=1;j<=n;j++){if(j==tmp[2]) sump[j]=sump[j-1];else sump[j]=sump[j-1]&a[j];}for(int j=n;j>=1;j--){if(j==tmp[2]) sums[j]=sums[j+1];else sums[j]=sums[j+1]&a[j];}for(int j=1;j<=n;j++){if(j==tmp[2]) continue;if(gcd(a[tmp[2]],a[j])>(sump[j-1]&sums[j+1])+x){ans1=tmp[2];ans2=j;break;}}if(!tag[tmp[1]]) tag[tmp[1]]=1,vis[a[tmp[1]]]--;if(!tag[tmp[2]]) tag[tmp[2]]=1,vis[a[tmp[2]]]--;}}if(ans1==-1){int res=a[1],g=-1;for(int i=2;i<=n;i++) res&=a[i];for(int i=m;i>=res+x+1;i--){int cnt=0;for(int j=i;j<=m;j+=i) cnt+=vis[j];if(cnt>=2){g=i;break;}}if(g!=-1){for(int i=1,now=0;i<=n;i++){if(vis[a[i]]&&a[i]%g==0){now++;if(now==1) ans1=i;else{ans2=i;break;}}}}}if(ans1==-1) cout << "NO\n";else{cout << "YES\n";cout << 2 << ' ' << a[ans1] << ' ' << a[ans2] << '\n';cout << n - 2;for(int i=1;i<=n;i++){if(i!=ans1&&i!=ans2) cout << ' ' << a[i];}cout << '\n';}}return 0;
}