首先分析不出啥性质,所以肯定是暴力优化😅
常见的暴力优化手段有均摊,剪枝,数据范围分治(points),答案值域分析之类的。
比较经典的题目是 CF1870E Another MEX Problem,可以用剪枝和分析值域两种方法通过
考虑剪枝,这个大佬 是剪枝高手,大家快去膜拜他🤩
首先,设 g = gcd 1 ≤ i ≤ n a i g=\gcd_{1\le i\le n} a_i g=gcd1≤i≤nai,然后对每个 a i a_i ai只保留 g g g中的质因数。发现此时本质不同的 a i a_i ai比较少,并且本质不同的质因数也比较少,考虑从这两方面入手
记质因数数目为 M M M, a i a_i ai的状态数为 m m m,显然 M ≤ 11 M\le 11 M≤11, m m m不太清楚,但是可以感性发现不会很大
发现对于相同的 a i a_i ai,只需要保留前 M M M个较小的 e i e_i ei即可,后面的都用不上。
同时注意到被操作的数不会超过 M M M,因此 D P DP DP复杂度为 O ( 3 M m M 2 ) O(3^MmM^2) O(3MmM2)
每次只加入一个 a i a_i ai太浪费了,可以考虑一次将相同的 a i a_i ai一起加进去,然后记录需要选择的 a i a_i ai数目的最小值。这样组外 D P DP DP的复杂度为 O ( 3 M m M ) O(3^MmM) O(3MmM),组内 D P DP DP的复杂度为 O ( 3 M m ) O(3^Mm) O(3Mm)。
当 M M M取遍所有值时,最大计算量在 1 0 8 10^8 108左右,可以通过。
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define db double
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=1e6+5;
int n,cnt;
ll K,a[N],nums[N],e[N],g,res;
int M;
ll prime[15];
vector<ll>v[15005];
ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);
}
int get(ll x){return lower_bound(nums+1,nums+1+cnt,x)-nums;
}
void dfs(int u,ll mul){if(u==M){nums[++cnt]=mul;return;}while(mul<=1000000000000/prime[u]){mul*=prime[u],dfs(u+1,mul);}
}
ll now[1<<11][12],nxt[1<<11][12],sm[12];
int dp[1<<11],h[1<<11];
ll b[15];
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>K;for(int i=1;i<=n;i++)cin>>a[i],g=gcd(g,a[i]);for(int i=1;i<=n;i++)cin>>e[i];ll tmp=g;for(int i=2;i<=tmp/i;i++){if(tmp%i==0){prime[M++]=i;while(tmp%i==0)tmp/=i;}}if(tmp>1)prime[M++]=tmp;dfs(0,1),sort(nums+1,nums+1+cnt);for(int i=1;i<=n;i++){ll tmp2=1;for(int j=0;j<M;j++){while(a[i]%prime[j]==0)a[i]/=prime[j],tmp2*=prime[j];}v[get(tmp2)].pb(e[i]);}memset(now,0x3f,sizeof now),now[0][0]=0;for(int i=1;i<=cnt;i++){if(v[i].size()==0)continue;sort(v[i].begin(),v[i].end());if(v[i].size()>M)v[i].resize(M);for(int j=0;j<v[i].size();j++)sm[j+1]=sm[j]+v[i][j];ll tmp=nums[i];for(int j=0;j<M;j++){b[j]=1;while(tmp%prime[j]==0)b[j]*=prime[j],tmp/=prime[j];}for(int j=0;j<1<<M;j++){for(int k=0;k<=M;k++){nxt[j][k]=now[j][k];}}for(int j=1;j<1<<M;j++){h[j]=0,dp[j]=114514;ll mul=1;for(int k=0;k<M;k++){if(j>>k&1)mul*=b[k];}if(mul<=K)h[j]=1;for(int k=j;k;k=(k-1)&j){if(h[k])dp[j]=min(dp[j],dp[j-k]+1);}if(dp[j]<=v[i].size()){int s=(1<<M)-1-j;for(int k=s;;k=(k-1)&s){for(int l=0;l<=M;l++){if(now[k][l]!=inf){nxt[k+j][l+dp[j]]=min(nxt[k+j][l+dp[j]],now[k][l]+sm[dp[j]]);}}if(k==0)break;}}}for(int j=0;j<1<<M;j++){for(int k=0;k<=M;k++){now[j][k]=nxt[j][k];}}}ll res=inf;for(int i=0;i<=M;i++)if(now[(1<<M)-1][i]!=inf)res=min(res,now[(1<<M)-1][i]*i);cout<<(res==inf?-1:res);
}