牛客多校第七场B题

题目链接 https://ac.nowcoder.com/acm/contest/5672/B

题意

　　比较晦涩，意思大概是，给定 n 和 m 。问你要一个序列。 这个序列尽可能短，同时令其字典序尽可能小。这个序列满足，可以将其划分为n个组使其值之和相等。也能划分为m个。

做法

　　逐步缩小问题的规模。对于一对 n（<）m   首先知道当m是n的倍数时，只需要将序列分为m组每组为n即可。当m不为n的倍数时。可以取k为小于m的最大的n的倍数。将序列先划分出k组每组为n的组。然后剩下了（m-k）*n个。 这样 就编成了 m-k与 n时的问题，同样的问题求解即可。类似于递归的思想。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N=2e6+10;
const int INF=0x3f3f3f3f;
const LL MOD=1e9+7;
int n,m;
vector<int>ans;
void solve(){
    while(n){
 
        int tmp=m-m%n;
        for(int i=1;i<=tmp;i++){
            ans.push_back(n);
        }
        m=m%n;
        if(n>m)swap(n,m);
    }
    int len=ans.size();
    printf("%d
",len);
    for(int i=0;i<len;i++){
        printf("%d ",ans[i]);
    }
    printf("
");
 
}
int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0),cout.tie(0);
    //freopen("1.in","r",stdin);
    //cout<<sqrt(29400)<<endl;
    int test;
    scanf("%d",&test);
    while(test--){
        ans.clear();
        scanf("%d%d",&n,&m);
        if(n>m)swap(n,m);
        solve();
    }
}