Codeforces Round #499 (Div. 1) C. Border || Codeforces Round #499 (Div. 2) E.Border(数论/贝祖定理)

题意:给你n个数字(十进制),每个数字都可以使用无限次,问你在k进制下,可以组合的到的目标和的尾数有哪些.

昨天下午打完多校感觉还是蛮累的,cf晚上11点的场子也不大想打,刚好室友想开小号随便打打,

我也就帮忙读了个题顺便嘴炮ac了一下(´・ω・`)

看到这道E的时候马上就想到了可以得到的尾数仅和用以组合的数的gcd有关,昨晚是这么(不严谨的)想的,假设n个数字的gcd为g,那么便可以发现所有的n个数都有

那么对于目标和来说相当于

最后的尾数则是

然后我就猜了一下正解就是

早上简单写了一下果然A了o(*≧▽≦)ツ

然后吧看了下出题人写的题解,发现了这么个东西:裴蜀定理(或贝祖定理,Bézout’s identity)

对于g=gcd(a,b),那么任意x,y都满足ax+by为g的整数倍

特别的,必定存在x,y满足ax+by=g

做一个小推广,那么便可以得到对于n个数字ai的gcd 必定存在满足如下等式的xi的集合

如果已知该定理,那么这道题就变的很简单了,正解就是如我不严谨的猜测一样为:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define inf int(0x3f3f3f3f)
#define mod int(1e9+7)
#define eps double(1e-6)
#define pi acos(-1.0)
#define lson  root << 1
#define rson  root << 1 | 1
 
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    int gcd=k;
    for(int i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        gcd=__gcd(gcd,x%k);
    }
    int cnt=0;
    printf("%d\n",k/gcd);
    while(cnt<k)
    {
        printf("%d ",cnt);
        cnt+=gcd;
    }
    printf("\n");
}