Codeforces #499 Div2 E (1010C) Border

一直第9个样例WA,发现事情没有这么简单的时候只剩20分钟了。。。。。。

看了一些大神提交的代码,发现还能这么玩。。。。。

这个题目可以转化成这个问题:给一堆[0,m)之间的数,可以随意组合成新的数(当然新的数要%m),问这个区间有多少个数?分别是哪些数?

解法:求所有数的(包括m)的gcd,那么元素个数就是m/gcd(所有的数),每个元素分别是gcd的倍数。

这种做法可以覆盖所有情况,因为求出所有数的gcd后,gcd的某一个倍数可以表示任何一个读入数,自然也可以表实任何读入的数的各种组合,而这个gcd是包含m的,所以包含所有读入的数的各种组合%m的情况。

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m,x;
	scanf("%d%d",&n,&m);
	int y=m;
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		x%=m;
		y=__gcd(x,y);
	}
	int num=m/y;
	cout<<num<<endl;
	for(int i=0;i<num;i++){
		printf("%d ",y*i);
	}
	cout<<endl;	 
}

  

原文地址:https://www.cnblogs.com/pkgunboat/p/9376871.html