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;
}