牛客多校訓練キャンプ2020第7場

C
标题:n*m件の品物は、いくつかの箱に分けて、それぞれの箱に任意の多くの品物を入れることができます.要求は、箱を分解しない前提の下で、物品をすべてm部に分けることができて、またすべてn部に分けることができます.考え方:転々として除去する

#include
#include
#include
#include
#include
#include
using namespace std;
const int N = 2e6+10;
int ans[N];
int cnt;
void dfs(int x, int y)
{
	if(y<x)	swap(x,y);
	if(x == 0)	return;
	for(int i = 1; i <= y/x *x;i++)
		ans[++cnt] = x;
	dfs(y%x, x);
 } 
int main()
{
	int T,n,m;
	scanf("%d",&T);
	while(T)
	{
		T--;cnt =0 ;
		scanf("%d%d",&n,&m);
		dfs(n,m);
		printf("%d
",cnt);
		for(int i = 1; i <= cnt; i++)
			printf("%d ",ans[i]);
		printf("
"); 
	}
	return 0;
}