CF1103D Professional layor

你谷假翻译害人不浅

考虑先求出所有数字的 $\gcd$ ，这个数必然不超过 $10^{12}$ ，所以不同的质因数个数不超过 $11$ （拿前12个质因数乘起来就已经 $7 \times 10^{12}$ 了）。

然后考虑，我们肯定要把这 $\gcd$ 的质因数分解分成很多块质数，让某些数不再是某块质数的倍数。然后可以发现，如果可以做到必然有答案小于 12 。

于是就有了一个最简单的 dp 方案：$dp[i][j][s]$ 表示前 $i$ 个数，已经对 $j$ 个数字进行了操作，当前 $\gcd$ 已经被处理的集合为 $s$ 时的贡献的和。

转移很简单，就是在每个位置枚举下子集，然后尝试一下是否可以把这个子集在这个数去掉。事先预处理每个集合是否可以这个数字去掉即可。复杂度是 $O(n3^mm)$ 的。无法通过这个题。

然后发现，只有当某个数字在与 $\gcd$ 有共同质因子的时候才有用，并且对于 $\gcd$ 的各个质因数在这个数字的幂次，如果相同，就是等价的，只需要保留前 $m$ 小就完事了。最后被出题人证明出这样的数字个数是不超过 $M = 12000$ 的。

但是其实貌似并不是证明得到的，出题人没明说，看了下下面的 Discuss 发现有人验证过：

$m$	$M$
$1$	$39$
$2$	$469$
$3$	$2369$
$4$	$6734$
$5$	$10808$
$6$	$11598$
$7$	$7815$
$8$	$3462$
$9$	$895$
$10$	$110$
$11$	$4$

其实还有一个剪枝。算对于当前这个数字某个集合是否可行的时候，可以考虑做一次与卷积，我们只拿尽量大的集合，因为既然是同一个数字拿小的集合肯定不如拿大的集合啊。这个不能优化复杂度但是优化了大概 600 ms..

反正就是个剪枝题。。有时候暴力 dp 搞出来复杂度有锅就可以想想能不能剪掉无用的数吧。。

于是最后复杂度证明出来是 $O(2^mmM + m^23^m)$ 。不是很懂这复杂度怎么来的。。网上也没找到相应题解（）。

cpp

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 1000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define min( a , b ) ( (a) < (b) ? (a) : (b) )
#define max( a , b ) ( (a) > (b) ? (a) : (b) )
typedef long long ll;
int n , m; long long k , G;
long long A[MAXN];
int E[MAXN];
vector<ll> fac;

inline long long gcd( ll a , ll b ) {
    return b ? gcd( b , a % b ) : a;
}

map<ll,vi> M;
int ok[MAXN];

inline void FWTand( int* A , int len ) {
    for( int mid = 2 ; mid <= len ; mid <<= 1 )
        for( int i = 0 ; i < len ; i += mid )
            for( int j = i ; j < i + ( mid >> 1 ) ; ++ j )
                A[j] += A[j + (mid >> 1)];
}

ll dp[12][( 1 << 11 ) + 6];

void solve() {
    cin >> n >> k;
    rep( i , 1 , n ) scanf("%lld",A + i) , G = !G ? A[i] : gcd( G , A[i] );
    rep( i , 1 , n ) scanf("%d",E + i);
    ll c = G;
    if( G == 1 ) return void( puts("0") );
    for( ll i = 2 ; i * i <= G ; ++ i ) if( c % i == 0 ) {
        while( c % i == 0 ) c /= i;
        fac.pb( i );
    }
    if( c != 1 ) fac.pb( c );
    m = fac.size();
    rep( i , 1 , n ) {
        ll t = 1 , a = A[i];
        rep( j , 0 , m - 1 ) while( a % fac[j] == 0 ) t *= fac[j] , a /= fac[j];
        M[t].pb( E[i] );
    }
    vi us;
    memset( dp , 0x3f , sizeof dp );
    dp[0][0] = 0;
    for( auto& t : M ) {
        sort( t.se.begin() , t.se.end() );
        long long x , y;
        rep( i , 1 , ( 1 << m ) - 1 ) {
            x = t.fi , y = 1;
            rep( j , 0 , m - 1 ) if( i & ( 1 << j ) )
                while( x % fac[j] == 0 ) x /= fac[j] , y *= fac[j];
            if( y <= k ) ok[i] = 1;
        }
        FWTand( ok , ( 1 << m ) );
        us.clear();
        rep( i , 0 , ( 1 << m ) - 1 ) { if( ok[i] == 1 ) us.pb( i ); ok[i] = 0; }
        for( auto& v : t.se ) {
            bool flg = 0;
            per( i , ( 1 << m ) - 1 , 0 )
                per( j , m - 1 , 0 )
                    for( auto& q : us )
                        if( dp[j + 1][i | q] > dp[j][i] + v )
                            dp[j + 1][i | q] = dp[j][i] + v , flg = 1;
            if( !flg ) break;
        }
    }
    long long res = 0x3f3f3f3f3f3f3f3f;
    rep( i , 1 , m ) if( dp[i][( 1 << m ) - 1] < 0x3f3f3f3f3f3f3f3f ) res = min( res , i * dp[i][( 1 << m ) - 1] );
    printf("%lld\n",res == 0x3f3f3f3f3f3f3f3f ? -1 : res);
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}