牛客多校训练营2020第7场

C

题意：n*m件物品，分装到一些盒子里，每个盒子可以装任意多的物品。要求，在不拆盒子的前提下，既能将物品均分成m份，又能均分成n份。
思路：辗转相除

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
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\n",cnt);
		for(int i = 1; i <= cnt; i++)
			printf("%d ",ans[i]);
		printf("\n"); 
	}
	return 0;
}

本文地址：https://blog.csdn.net/micaudience/article/details/107938908