题面在这里
题意:求n∑i=1aixi mod k的所有取值,xi为任意自然数
考虑裴蜀定理的一般形式: n∑i=1aixi=C 有解,当且仅当ngcdi=1ai|C 那么令ngcdi=1ai=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; }
|
v1.1.9-beta9