本文主要是介绍Codeforces Round #499 (Div. 2)E. Border(裴蜀定理)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://codeforces.com/contest/1011/problem/E
题目大意：有n种纸币，每种纸币有a[i]的面额，所有纸币无限，问所有可能的搭配转成k进制数后的最后一位有几种情况并输出
题目思路：转成k进制数后的最后一位即结果%k，由裴蜀定理a1*x1 + a2*x2 +...+ an * xn = c 有整数解，必有gcd(a1, a2,...,an) | c，那么我们只需要求出gcd，然后让gcd*0~k-1(代码里图打得方便多乘了k，效果是跟0一样可以忽略)，就能得到所有可能情况，然后用set去重即可
以下是代码：
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define ll long long
const ll MAXN = 1e5+5;
const ll MOD = 1e9+7;
ll n,k,a[MAXN];
set<ll>s;
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);
}
int main()
{while(~scanf("%I64d%I64d",&n,&k)){ll c=0;rep(i,1,n){scanf("%I64d",&a[i]);c=gcd(a[i],c);}s.clear();rep(i,0,k){s.insert(c*i%k);}cout<<s.size()<<endl;for(set<ll>::iterator iter=s.begin();iter!=s.end();iter++){cout<<*iter<<" ";}cout<<endl;}return 0;
}
这篇关于Codeforces Round #499 (Div. 2)E. Border(裴蜀定理)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
