这个定理就像类似学扩展欧几里得判断是否有解的条件，当时是ax+by = c；仅当c = k*gcd（a,b)时有解，其实也就是只要是公约数的倍数就行。
而裴蜀定理是多个未知量x1*a1+x2*a2+...xn*an = c， 也是仅当 c = k * gcd(a1, a2....an)时有解。
思路：求出gcd，然后枚举所有解的可能就行了。也就是令k = 1 2 3 ....
下面的代码枚举到k是因为，枚举到k+1时和枚举1时一样的，（gcd*k + gcd）% k = gcd%k;
#include <bits/stdc++.h> #define ll long long using namespace std; set<int> ma; int main(){ ll n, k, x, g; cin >> n >> k >> g; for(int i = 2; i <= n; i++){ cin >> x; g = __gcd(g, x); } for(ll i = 1; i <= k; i++) ma.insert(i*g%k); cout << ma.size() << endl; for(auto it = ma.begin(); it != ma.end(); it++) cout << *it << ' '; return 0; }
转载于:https://www.cnblogs.com/philo-zhou/p/11348581.html
相关资源：JAVA上百实例源码以及开源项目