![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsICM38FdsYkRGZkRG9lcvx2bjxiNx8VZ6l2cs0TVHRGa1cVY0lTbiVHbywEMW1mY1RzRapnTtxkb5ckYplTeMZTTINGMShUYfRHelRHLwEzX39GZhh2css2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xyayFWbyVGdhd3LcV2Zh1Wa9M3clN2byBXLzN3btg3Pn5GcuQTO3EjM1EjM2ADOwAjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
题目大意:
给定n*m个口罩,需要将这些口罩封装成盒, 有n个a类医院,m个b类医院,从这些盒子中可以找到n组口罩,这n组盒子中口罩数量一样多,也可以找到m组口罩,这m组口罩数量一样多,要求分组尽量少,并且字典序尽量大。
题目思路:
gcd递归构造最优解
#include<iostream>
using namespace std;
long long num,t,n,m,ans[100005];
void gcd(int a,int b)
{
if(b==0)
return;
for(int i=0;i<(a/b)*b;i++)
{
ans[num++]=b;
}
gcd(max((a%b),b),min((a%b),b));
}
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m;
if(n<m)
swap(n,m);
num=0;
gcd(n,m);
printf("%lld\n",num);
for(int i=0;i<num;i++)
{
printf("%lld ",ans[i]);
}
printf("\n");
}
return 0;
}