题意

给定\(n\)个砝码和\(m(1 \le n, m \le 100000)\)个背包\((1 \le n_i, m_i \le 1000000000)\)，保证对于任意两个砝码都有一个是另一个的正整数倍，求最多拿走多少砝码。

分析

砝码的种类不会超过\(30\)种。

小的肯定在大的前面放。

题解

分出\(s\)种种类后，我们将背包用\(s\)个数的进制来表示。那么从小到大地放，如果当前进制的系数不够了，则向前面借位，依次类推。

#include 
    
     using namespace std;inline int getint() {    int x=0, c=getchar();    for(; c<48||c>57; c=getchar());    for(; c>47&&c<58; x=x*10+c-48, c=getchar());    return x;}const int N=100005;int a[N], b[N], s[35], c[35];int main() {    int n=getint(), m=getint();    for(int i=1; i<=n; ++i) {        a[i]=getint();    }    for(int i=1; i<=m; ++i) {        b[i]=getint();    }    sort(b+1, b+1+m);    int tot=0;    for(int i=1; i<=m; ++i) {        if(b[i]!=b[i-1]) {            b[++tot]=b[i];        }        ++s[tot];    }    for(int i=1; i<=n; ++i) {        for(int j=tot; j; --j) {            c[j]+=a[i]/b[j];            a[i]%=b[j];        }    }    int ans=0;    for(int i=1; i<=tot; ++i) {        for(int j=i+1; j<=tot && s[i]>c[i]; ++j) {            int cost=b[j]/b[i], rest=s[i]-c[i], need=(rest+cost-1)/cost;            if(need<=c[j]) {                c[j]-=need;                rest=(need*cost-rest)*b[i];                c[i]=s[i];                for(int k=j; k>i; --k) {                    c[k]+=rest/b[k];                    rest%=b[k];                }            }            else {                c[i]+=c[j]*cost; c[j]=0;            }        }        ans+=min(s[i], c[i]);    }    printf("%d\n", ans);    return 0;}