伸手可触的『今天」安抚静脉的跃动声

· · 题解

CF1103D

难点在于打表。

设所有 a_i 的质因数分解结果只保留与 \gcd 质因数分解得到的幂级数集合交，暂且称为 a_i 关于 \gcd 的质因数分解，以此作为等价类划分，设 \gcd 质因数分解结果存在 k 个质数。

一个一眼的贪心：选了一个数一定要消掉至少一个质数。所以总的选择的数的个数至多为 m 个，直接设 dp_{i,S} 表示选择了 i 个数消掉的质因数集合为 S 的最小花费。

最暴力的转移：直接枚举选每个数和这个数消掉的质因数集合。一个很 naive 的剪枝是发现对于每个等价类只用保留前 m 小的数即可。

然后你发现你现在的转移很巨大多恐怖，于是你放弃思考写了这个看起来很暴力的做法发现过了。

经打表检验，所有等价类保留前 m 个后产生的数的个数数量级为 12000，设为 N，那么最后的时间复杂度只有 O(N k^2 3 ^ k)，然后就莫名跑过了，难点果然在于打表。

/*
先把 gcd 求出来，然后钦定每个质因数对应哪个被选择的数就行了
但是这个预处理好像很困难。容我晚上想想。
*/
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int Len = 1e6 + 5 , Inf = 1e15;
int n,k,m,a[Len],e[Len],f[20][(1 << 13) + 5];
inline int read() {
    char ch = getchar();
    int x = 0, f = 1;
    while (ch < '0' || ch > '9') ch = getchar();
    while ('0' <= ch && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
int gcd(int a,int b)
{
    if(!b) return a;
    return gcd(b , a % b);
}
vector<int> Pm;
map<int,vector<int> > vc;
map<int,vector<int> >::iterator it;
signed main()
{
    n = read() , k = read();int GCD = 0;
    for(int i = 1 ; i <= n ; i ++) a[i] = read() , GCD = gcd(a[i] , GCD);
    for(int i = 1 ; i <= n ; i ++) e[i] = read();
    if(GCD == 1) return puts("0") & 0; 
    for(int i = 2 ; i * i <= GCD ; i ++) while(GCD % i == 0) Pm.push_back(i) , GCD /= i;
    if(GCD != 1) Pm.push_back(GCD);
    sort(Pm.begin() , Pm.end());
    Pm.erase(unique(Pm.begin() , Pm.end()) , Pm.end());
    m = (int)Pm.size();
    for(int i = 1 ; i <= n ; i ++) 
    {
        int ns = 1;
        for(int j = 0 ; j < m ; j ++) while(a[i] % Pm[j] == 0) ns = ns * Pm[j] , a[i] /= Pm[j];
        vc[ns].push_back(e[i]);
    }
    for(int i = 0 ; i <= m ; i ++) for(int j = 0 ; j < (1 << m) ; j ++) f[i][j] = Inf;
    f[0][0] = 0;
    for(it = vc.begin() ; it != vc.end() ; it ++)
    {
        vector<int> N;N = it -> second;int w = it -> first;
        sort(N.begin() , N.end());
        vector<int> A;
        for(int s = 0 ; s < (1 << m) ; s ++)
        {
            int ds = 1 , ww = w;
            for(int i = 0 ; i < m ; i ++) 
            {
                if((s >> i) & 1)
                {
                    while(ww % Pm[i] == 0) ds = ds * Pm[i] , ww /= Pm[i];
                }
            }
            A.push_back(ds);
        }
        const int SS = (int)N.size();
        for(int p = 0 ; p < min(SS , m + 1) ; p ++) 
        {
            int sw = N[p];bool bot = 0;
            for(int i = m - 1 ; i >= 0 ; i --)
                for(int j = 0 ; j < (1 << m) ; j ++)
                {
                    int NT = (1 << m) - 1 - j;
                    //printf("%d %d\n",j,A[j]);
                    for(int T = NT ; T ; T = (T - 1) & NT) 
                    {
                        if(A[T] <= k && f[i + 1][j | T] > f[i][j] + sw) 
                        {
                            f[i + 1][j | T] = f[i][j] + sw;
                            bot = 1;
                        }
                    }
                }
            if(!bot) break;
        }
    }
    int as = Inf;
    for(int i = 1 ; i <= m ; i ++) as = min(as , f[i][(1 << m) - 1] * i);
    printf("%lld\n",(as == Inf) ? -1 : as);
    return 0;
}