【题解】CF1103DProfessional layer
神题做前先(orzyyb)
一个很好的性质(之前也见过但是没有想到的)
zhengchu
(gcdle 10^{12}) 所以不同的质因数(le 12)
所以对这(12)个质因数状压。
所以答案显然小于等于(12)
对于每个数，只有因数和全局(gcd)有关的才有用，其余没用。
所以每种数(意会一下，就是和(gcd)关系一样的数)最多只需要(12)个，所以可以把(n)将下来。
然后就愉快地(dp)了(说的轻巧)
设(dp(i,STATE))表示已经选用了(i)个数，现在(gcd)的质因数还剩(STATE)的状态
假如一个状态转移了(ge 13)次，那么一定是不优的。开个数组记录顺便剪枝。转移方程
[dp(i,k' subset k)=min{ dp(i-1,k)+e[i]},(cnt(k)<13)
]
[dp(0,0)=0
]
实际上(13)可以优化到(d)全局(gcd)的质因数个数(m)
有一个状压的技巧，如何枚举子集？$j subset k $
- 知道(j)
for(register int k=(j+1)|j;k<=S;k=(k+1)|j)
- 知道(k)
for(register int j=(k-1)&k;j;j=(j-1)&k)
上抄zsy的代码
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
#define DRP(t,a,b) for(register ll t=(a),edd=(b);t>=edd;--t)
#define RP(t,a,b) for(register ll t=(a),edd=(b);t<=edd;++t)
#define ERP(t,a) for(register ll t=head[a];t;t=e[t].nx)
#define pu(x) seg[x]=seg[(x)<<1]+seg[(x)<<1|1]
#define lef l,mid,pos<<1
#define rgt mid+1,r,pos<<1|1
#define all 1,n,1
#define re register
#define midd register int mid=(l+r)>>1
#define TMP template < class ccf >
TMP inline ccf qr(ccf b){
register char c=getchar();register int q=1;register ccf x=0;
while(c<48||c>57)q=c==45?-1:q,c=getchar();
while(c>=48&&c<=57)x=x*10+c-48,c=getchar();
return q==-1?-x:x;}
TMP inline ccf Max(ccf a,ccf b){return a<b?b:a;}
TMP inline ccf Min(ccf a,ccf b){return a<b?a:b;}
TMP inline ccf Max(ccf a,ccf b,ccf c){return Max(a,Max(b,c));}
TMP inline ccf Min(ccf a,ccf b,ccf c){return Min(a,Min(b,c));}
TMP inline void Swap(ccf& a,ccf& b){re ccf c=b;b=a;a=c;}
TMP inline void READ(ccf* _arr,int _n){RP(t,1,_n)_arr[t]=qr((ccf)1);}
//----------------------template&IO---------------------------
const int maxn=1e6+15;
//const ll mod=1e9+7;
inline ll gcd(ll x,ll y){
for(register ll t=x;y;t=y,y=x%y,x=t);
return x;
}
int n,m,S,e[maxn],vis[1<<12];
ll d,k,a[maxn],p[maxn],f[13][1<<12],ans,inf;
map < ll ,vector<int> >mp;
int main(){
#ifndef ONLINE_JUDGE
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
#endif
n=qr(1);k=qr(1ll);
RP(t,1,n) d=gcd(a[t]=qr(1ll),d);
RP(t,1,n) e[t]=qr(1ll);
for(register ll t=2;t*t<=d;++t){
if(d%t==0){
p[m++]=t;
while(d%t==0) d/=t;
}
}
if(d>1) p[m++]=d;
S=(1<<m)-1;
RP(t,1,n){
register ll temp=1;
RP(k,0,m-1){
while(a[t]%p[k]==0) a[t]/=p[k],temp*=p[k];
}
mp[temp].push_back(e[t]);
}
memset(f,63,sizeof f);
ans=inf=f[0][0];f[0][0]=0;
for(register auto pr:mp){
ll x=pr.first;sort(pr.second.begin(),pr.second.end());
if((int)pr.second.size()>m) pr.second.resize(m);
RP(t,0,S){
ll y=x,z=1;
RP(i,0,m-1)
if(t>>i&1)
while(y%p[i]==0) y/=p[i],z*=p[i];
vis[t]=(z<=k);
}
for(register auto cost:pr.second){
register bool fg=0;
for(register int i=m-1;~i;--i)
for(register int j=0;j<=S;++j)
if(f[i][j]<inf)
for(register int k=(j+1)|j;k<=S;k=(k+1)|j)
if(vis[k^j])
if(f[i+1][k]>f[i][j]+cost)
fg=1,(f[i+1][k]=f[i][j]+cost);
if(not fg) break;
}
}
RP(t,0,m)if(f[t][S]<inf) ans=Min(ans,f[t][S]*t);
if(ans==inf) puts("-1");
else cout<<ans<<endl;
return 0;
}
// orz zsy