题解 | #小苯的前缀gcd构造#

一边往数组里放数，一边让前缀 gcd 只会往“更小的约数”走，再用 DP 记录当前前缀 gcd 和已经凑出来的权值，最后看看能不能刚好凑到 x。

void solve(){
    int n,m,x;cin>>n>>m>>x;
    if(x<n||x>n*m){
        cout<<-1<<endl;
        return;
    }
    vvi d(m+1);
    for(int i=1;i<=m;++i){
        for(int j=1;j<=i;++j){
            if(i%j==0){
                d[i].push_back(j);
            }
        }
    }
    vvi cur(m+1,vi(x+1,0)),nxt(m+1,vi(x+1,0));
    vector<vvi> pre(n+1,vvi(m+1,vi(x+1,-1)));
    for(int i=1;i<=m;++i){
        if(i<=x){
            cur[i][i]=1;
            pre[1][i][i]=0;
        }
    }
    for(int len=1;len<n;++len){
        for(int i=1;i<=m;++i){
            for(int j=1;j<=x;++j){
                if(!cur[i][j]){
                    continue;
                }
                for(int k:d[i]){
                    int s=j+k;
                    if(s<=x&&!nxt[k][s]){
                        nxt[k][s]=1;
                        pre[len+1][k][s]=i;
                    }
                }
            }
        }
        cur.swap(nxt);
        for(int i=1;i<=m;++i){
            fill(all(nxt[i]),0);
        }
    }
    int g=-1;
    for(int i=1;i<=m;++i){
        if(cur[i][x]){
            g=i;
            break;
        }
    }
    if(g==-1){
        cout<<-1<<endl;
        return;
    }
    vi ans(n+1);
    int s=x;
    for(int len=n;len>=1;--len){
        ans[len]=g;
        if(len>1){
            int p=pre[len][g][s];
            s-=g;
            g=p;
        }
    }
    for(int i=1;i<=n;++i){
        cout<<ans[i]<<" ";
    }
    cout<<endl;
}