题解 CF1687E【Become Big For Me】
whiteqwq
·
·
题解
CF1687E Become Big For Me
更好的阅读体验
题意
你有一个变量 v 初始值为 1，你还有一个集合 A，每次可以选择 A 的一个子集并让 v 乘或除这个集合的 \text{lcm}，你要使得最后 v 的值变为：
\gcd_{i\ne j}\{A_i\times A_j\}
## 分析
这道题是我听物理课时偶然想到的，挺喜欢这个 idea，就把它投到了 [CF](https://codeforces.com/contest/1687) 上，感觉区分度还可以。
竟然被评为了 \*3500，受宠若惊。
感谢 [SSerxhs](https://www.luogu.com.cn/user/29826) 神仙对做法的完善/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](https://codeforces.com/blog/entry/103493)。
选择一个答案不变的集合，只需要依据上述方法选出一个 $\gcd$ 不变的集合，将其去除之后再选一遍即可，这样集合大小不会超过 $14$，对这个集合施用上面的算法即可通过。
## 代码
```
#include<bits/stdc++.h>
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];
vector<int>S;
set<int>s;
map<int,int>use;
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(c<mnexp[x])
mnexp[x]=c,recmn[x]=id;
}
void solve(){
for(int i=1;i<=n;i++)
if(ok[i]==0){
int v=a[i];
stp++;
while(v>1){
int p=mn[v],c=0;
while(v%p==0)
v/=p,c++;
vis[id[p]]=stp,chk(id[p],i,c);
}
set<int>::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<S.size();i++)
for(int j=i+1;j<S.size();j++)
g=gcd(g,1ll*a[S[i]]*a[S[j]]);
if(g==1){
puts("0");
return 0;
}
for(int i=1;i<(1<<S.size());i++){
int mul=__builtin_parity(i)==1? 1:-1;
ans+=(abs(mul+(-mul)*(__builtin_popcount(i)-1)));
}
printf("%d\n",ans);
int tot=0;
for(int i=1;i<(1<<S.size());i++){
int mul=__builtin_parity(i)==1? 1:-1,cnt=__builtin_popcount(i);
int v=mul+(-mul)*(cnt-1),V=abs(v);
for(int j=1;j<=V;j++){
printf("%d %d ",v==V? 0:1,cnt);
tot+=(v==V? 0:1,cnt);
for(int j=0;j<S.size();j++)
if((i>>j)&1)
printf("%d ",S[j]);
puts("");
}
}
return 0;
}
```
## 彩蛋
