CF1687E Become Big For Me 出题报告
CF1687E Become Big For Me
更好的阅读体验
题意
你有一个变量 \(v\) 初始值为 \(1\)，你还有一个集合 \(A\)，每次可以选择 \(A\) 的一个子集并让 \(v\) 乘或除这个集合的 \(\text{lcm}\)，你要使得最后 \(v\) 的值变为：
\[\gcd_{i\ne j}\{A_i\times A_j\} \]\(2\leqslant |A|\leqslant 10^5,A_i\leqslant 10^6\)，操作总数不能超过 \(10^5\)，操作集合大小之和不能超过 \(10^6\)。
分析
这道题是我听物理课时偶然想到的，挺喜欢这个 idea，就把它投到了 CF 上，感觉区分度还可以。
竟然被评为了 *3500，受宠若惊。
感谢 SSerxhs 神仙对做法的完善/bx/bx/bx！
考虑将 \(\gcd_{i\ne j}\{A_i\times A_j\}\) 转化一下，其可以表示为所有质因子最小和次小（非严格）幂次的乘积。
类似 \(\gcd-\text{lcm}\) 反演，我们对其施加广义 \(\min-\max\) 容斥，可得：
\[\gcd_{i\ne j}\{A_i\times A_j\}=\prod_{T\subseteq U}\text{lcm}(T)^{(-1)^{|T|}(|T|-2)} \]于是我们得到了一个 \(O(2^nn)\) 次操作的解法。
一个经典结论是对于任意值域 \([1,10^6]\) 的集合 \(S\)，其都存在一个大小为 \(7\) 的子集使得 \(\gcd\) 等于 \(\gcd(S)\)。（\(V\) 为值域）
构造则可以任选一个数，将其最小幂次对应的数加入集合，再检查这个数能否去除即可，正确性见 CF。
选择一个答案不变的集合，只需要依据上述方法选出一个 \(\gcd\) 不变的集合，将其去除之后再选一遍即可，这样集合大小不会超过 \(14\)，对这个集合施用上面的算法即可通过。
代码
#include
using namespace std;
const int maxn=100005,maxv=1000005,maxp=80005;
int n,ps,mnv,stp,ans;
int a[maxn],p[maxp],c[maxv],mn[maxv],id[maxv],zero[maxn],vis[maxp],ok[maxn],flg[maxn],mnexp[maxp],recmn[maxp];
vectorS;
sets;
mapuse;
void sieve(int n){
c[1]=1;
for(int i=2;i<=n;i++){
if(c[i]==0)
p[++ps]=i,id[i]=ps,mn[i]=i,s.insert(ps),mnexp[ps]=1000,zero[ps]=-1;
for(int j=1;j<=ps&&i*p[j]<=n;j++){
c[i*p[j]]=1,mn[i*p[j]]=p[j];
if(i%p[j]==0)
break;
}
}
}
inline void chk(int x,int id,int c){
if(c1){
int p=mn[v],c=0;
while(v%p==0)
v/=p,c++;
vis[id[p]]=stp,chk(id[p],i,c);
}
set::iterator it=s.begin();
while(it!=s.end()){
if(vis[*it]==stp)
it++;
else zero[*it]=i,s.erase(it++);
}
}
for(int i=1;i<=ps;i++)
if(zero[i]!=-1)
chk(i,zero[i],0);
int st=1;
while(ok[st])
st++;
int v=a[st],chs=0;
while(v>1){
int p=mn[v],c=0;
while(v%p==0)
v/=p,c++;
if(mnexp[id[p]]!=c){
if(ok[recmn[id[p]]]==0)
chs++;
ok[recmn[id[p]]]=1;
}
}
if(chs<7)
ok[st]=1;
}
long long gcd(long long a,long long b){
return b==0? a:gcd(b,a%b);
}
int main(){
sieve(1000000),scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
solve();
s.clear();
for(int i=1;i<=ps;i++)
s.insert(i),mnexp[i]=1000,recmn[i]=0,zero[i]=-1;
solve();
for(int i=1;i<=n;i++)
if(ok[i])
S.push_back(i);
long long g=0;
for(int i=0;i>j)&1)
printf("%d ",S[j]);
puts("");
}
}
return 0;
}