P9589 「PFLOI R1」PFL 除法 题解

· · 题解

验题人题解。

讲个笑话，出题人最早打的是 O(nm)，还被 ddxrS 叉了。

然后在一阵口胡之下成了第一发正解。

如果正向求所有情况的最小次数，很难处理，于是考虑枚举每一种情况然后求这一种情况的最小次数。

考虑枚举最后所有数都变成的数 D，那么就会有 D\mid \min\{A\}，当然如果存在 i 使得 D\nmid A_i 的情况除外。

那么现在就是求 \sum\limits_{i=1}^n step(A_i\to D)。

那么对于 A_i，我们相当于要除以一个 x=\dfrac{a_i}{D}，问题就转化为了 B 中子序列乘积为 x 的最短长度。

那么问题就转化为了一个背包，如果直接背包，复杂度是 O(n^2) 级别的，考虑优化。

若存在 i,j 使得 B_i=B_j，那么 i,j 就是等价的，于是对 B 去个重。

那么这个时候时间复杂度就是 O(n+\dfrac{n}{2}+\cdots+\dfrac{n}{m})，是一个调和级数，那么整体的时间复杂度就是 O(n\log n)。

讲个笑话，这个题原数据甚至不去重或者不 sort 直接 unique 都能过。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N=5e5+5;
int n,m,ans=inf,a[N],b[N],V,dp[N];
inline int get(int x){
    int s=0;
    for(int i=1;i<=n;++i){
        if(a[i]%x)
            return inf;
        if(dp[a[i]/x]==inf)
            return inf;
        s+=dp[a[i]/x];
    }
    return s;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>a[i],V=max(V,a[i]);
    for(int i=1;i<=m;++i)
        cin>>b[i],V=max(V,b[i]);
    sort(a+1,a+n+1);
     sort(b+1,b+m+1);
     m=unique(b+1,b+m+1)-b-1;
    memset(dp,inf,sizeof(dp)),dp[1]=0;
    for(int i=1;i<=m;++i)
        for(int s=b[i];s<=V;s+=b[i])
            dp[s]=min(dp[s],dp[s/b[i]]+1);
    for(int i=1;i<=a[1]/i;++i)
        if(a[1]%i==0)
            ans=min({ans,get(i),get(a[1]/i)});
    if(ans==inf)
        ans=-1;
    cout<<ans<<endl;
    return 0;
}