Codeforces 1011E Border

题面在这里

题意:求i=1naixi mod k的所有取值,xi为任意自然数

考虑裴蜀定理的一般形式: i=1naixi=C gcdi=1nai|C 那么令gcdi=1nai=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;
}
Emoji | 预览
Markdown is supported
    Code -1: -1
    Powered By Valine
    v1.1.9-beta9