Codeforces 1011E Border

题面在这里

题意：求$\sum\limits_{i=1}^n a_ix_i\text{ mod k}$的所有取值，$x_i$为任意自然数

​

考虑裴蜀定理的一般形式： $$\sum_{i=1}^n a_ix_i=C\ 有解，当且仅当\gcd\limits_{i=1}^na_i | C$$ 那么令$\gcd\limits_{i=1}^na_i=G$，所有$G$的倍数就是能取到的值了

​

示例程序：

#include<cstdio>

const int maxn=100005;
int n,K,a[maxn];
inline int gcd(int x,int y) {return y==0?x:gcd(y,x%y);}
int main(){
	scanf("%d%d",&n,&K);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	int g=K;
	for (int i=1;i<=n;i++) g=gcd(g,a[i]);
	printf("%d\n",K/g);
	for (int i=0;i<K;i+=g) printf("%d ",i);
	return 0;
}