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\)的倍数就是能取到的值了

示例程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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;
}