【裴蜀定理】Border

Step1 Problem

原题有n种类型的纸币，以十进制给出，每种纸币能无限使用，转换成k进制数，求有末尾的数有多少种可能。

Step2 Ideas:

首先一个数转换成k进制数末尾的数为num%k, 由裴蜀定理可知 a1*x1 + a2*x2 +...+ an * xn = c 有整数解，必有c为gcd(a1, a2,...,an)的整数倍, 所以最后结果就是 i*gcd % k (0 <= i < k)不同数的集合。

Step3 Code:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<bitset>
 6 #include<cassert>
 7 #include<cctype>
 8 #include<math.h>
 9 #include<cstdlib>
10 #include<ctime>
11 #include<deque>
12 #include<iomanip>
13 #include<list>
14 #include<map>
15 #include<queue>
16 #include<set>
17 #include<stack>
18 #include<vector>
19 #define lt k<<1
20 #define rt k<<1|1
21 #define lowbit(x) x&(-x)
22 #define lson l,mid,lt
23 #define rson mid+1,r,rt
24 using namespace std;
25 typedef long long  ll;
26 typedef long double ld;
27 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
28 #define mem(a, b) memset(a, b, sizeof(a))
29 //#define int ll
30 const double pi = acos(-1.0);
31 const double eps = 1e-6;
32 const double C = 0.57721566490153286060651209;
33 const ll mod = 3e7;
34 const int inf = 0x3f3f3f3f;
35 const ll INF = 0x3f3f3f3f3f3f3f3f;
36 const int maxn = 5e3 + 5;
37 set<ll> se;
38 
39 int main() {
40     int n, k;
41     cin >> n >> k;
42     int sum = 0;
43     for (int i = 1; i <= n; i++) {
44         int x;
45         cin >> x;
46         sum = __gcd(sum, x);
47     }
48     for (int i = 0; i < k; i++)  se.insert(((ll)i * sum) % k);
49     cout << se.size() << endl;
50     for (auto it : se) cout << it << ' ';
51     return 0;
52 }

【 裴蜀定理 】Border

【裴蜀定理】Border