[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$等等。
更多输入输出样例请见选手下发文件夹。

数据范围:

对于所有数据,$1leqslant nleqslant 5 imes {10}^5,1leqslant kleqslant {10}^6,1leqslant a_ileqslant {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++

原文地址:https://www.cnblogs.com/wzc521/p/11464984.html