[CSP-S模拟测试]:math（裴蜀定理）

题目传送门（内部题22）

输入格式

第一行有$2$个整数$n,k$。
第二行有$n$个正整数$a_i$。

输出格式

第一行有一个整数$s$，表示可以生成的非负整数的个数。
第二行有$s$个可以生成的非负整数。

样例

样例输入：

2 8
4 12

样例输出：

2
0 4

数据范围与提示

样例解释：

有无穷种方案可以得到$x=0$，例如：
$b_1=0$、$b_2=0$，$b_1=2$、$b_2=0$，$b_1=1$、$b_2=1$等等。
有无穷种方案可以得到$x=4$，例如：
$b_1=1$、$b_2=0$，$b_1=1$、$b_2=2$，$b_1=3$、$b_2=4$等等。
更多输入输出样例请见选手下发文件夹。

数据范围：

对于所有数据，$1\leqslant n\leqslant 5\times {10}^5,1\leqslant k\leqslant {10}^6,1\leqslant a_i\leqslant {10}^9$。

题解

利用裴蜀定理（找规律）可以发现所有能生成的数都是$k$和所有$a_i$的$gcd$且比$k$小，于是我们就$A$掉这道题了。

时间复杂度：$\Theta(n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int k,x,g,i;

main()

{

	cin>>x>>k;

	g=k;

	while(cin>>x)g=__gcd(g,x);

	cout<<k/g<<endl;

	while(i<k)cout<<i<<' ',i+=g;

}

rp++

巴特西