当前位置： 移动技术网 > 移动技术>移动开发>IOS > 牛客多校训练营2020第7场

牛客多校训练营2020第7场

2020年08月12日  | 移动技术网移动技术  | 我要评论

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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网