号家军集训数论选做

讲师：朱富海（南京大学教授）

Strange Limit

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/gym/100204

形式化题意：存在一个函数，具体定义如下：

$f(i)= \begin{cases} p&,i=1\\ p^{f(i-1)}&,i\geq 2 \end{cases}$

定义，求。保证有解。

文件输入输出：limit
数据范围：，其中是质数。

诈骗题。

既然保证有解，我们就直接暴力求即可，但是你发现因为模数变化在特定情况（~~咬牙切齿~~）下会找不到解，然后你跑完发现当且仅当时会出现这种情况，那直接特判。

如果你考场遇到这道题你闲的没事甚至可以手玩打表直接切。

AC Code

// ----- Eternally question-----
// Problem: E - Strange Limit
// Contest: 2004-2005 Summer Petrozavodsk Camp, Andrew Stankevich Contest 7 (ASC 7)
// URL: https://codeforces.com/gym/100204/submit
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-28 14:47:49
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=13;
const int Phi[]={0,1,1,2,8,32,192,1152,9216,82944,829440,8294400,99532800};
ll P,Mul=1,M;
inline ll qPow(ll a,ll b,ll p)
{
	ll res=1;
	for(;b;b>>=1,a=a*a%p) (b&1)&&(res=res*a%p);
	return res;
}
inline void solve(ll p,ll m)
{
	if(m==2) return puts(p&1?"1":"0"),void();
	Mul=1;
	for(int i=2;i<=m;++i) Mul*=i;
	ll mul=p%Phi[m];
	for(int lst=-1,i=100;i--;)
	{
		mul=qPow(p,mul,Mul);
		if(mul==lst) return write(mul,'\n');
		lst=mul;//write(mul,' ');
	}
}
int main()
{
	freopen("limit.in","r",stdin);
	freopen("limit.out","w",stdout);
	read(P,M);
	solve(P,M);
	return 0;
}
/*

*/

矩阵游戏

题目简介

题目名称：矩阵游戏
题目来源：

评测链接：https://www.luogu.com.cn/problem/P1397

形式化题意：存在一个函数定义如下：

$f(i,j)= \begin{cases} 1&,i=1,j=1\\ af(i,j-1)+b &,j\geq 2\\ cf(i-1,m)&,i\geq 2,j=1 \end{cases}$

容易发现，函数构成了一个的表格，求。对取模。

数据范围：

考虑这个神秘的数据范围，大概是一个矩阵加速，所以我们来推矩阵递推式。首先考虑每一行的转移，视为，所以构造一个的初始矩阵：

$A= \begin{bmatrix} f_{1,1} & 1 \end{bmatrix}$

那么转移矩阵：

$I_1= \begin{bmatrix} a & 0 \\ b & 1 \end{bmatrix}$

那么就有：

$A\ast {I_1}^{m-1}= \begin{bmatrix} f_{1,m} & 1 \end{bmatrix}$

类似地，我们可以推出行与行之间的转移：

$I_2= \begin{bmatrix} c & 0 \\ d & 1 \end{bmatrix}$

所以，最终我们就有：

$A\ast \left( {I_1}^{m-1}\ast I_2 \right)^{n-1}\ast I_1= \begin{bmatrix} f(n,m) & 1 \end{bmatrix}$

然后你发现这样是对的，用矩阵快速幂就可以过掉的点。然后我们在快读中取模，注意欧拉定理定理，所以取模应该是。

然后提交却只有，还过不了。

我们考虑这个转移是一个一元递推数列的形式，也就是，那我们直接找不动点，求特征方程的根。

根据求解，不动点，这意味着当时不动点不存在，很显然，这时递推方程是一个等差数列。

所以，当时，该数列的特征方程没有不动点，也就没有逆元，所以欧拉定理无解。那至于怎么处理，发现此时，这意味着此时幂次的模数也是。

所以我们可以直接特判。时间复杂度。

正经解释好像是有关行列式和矩阵求逆的，我不会，详见洛谷题解区。

AC Code

// ----- Eternally question-----
// Problem: P1397 [NOI2013] 矩阵游戏
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1397
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-28 15:34:01
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
#define int long long
const int MAXN=1e6+10;
const int Mod=1e9+7,Mod2=1e9+6;
int N,M,A,B,C,D,pN,pM;
inline void add(int &x,int y){ x=x+y>=Mod?x+y-Mod:x+y; }
struct Matrix
{
	int a[4][4],n,m;
	Matrix(){ std::memset(a,0,sizeof(a)); }
	friend Matrix operator*(Matrix a,Matrix b)
	{
		Matrix res;
		int I=a.n,J=b.m;
		for(int i=1;i<=I;++i)
			for(int j=1;j<=J;++j)
				for(int k=1;k<=a.m;++k)
					add(res.a[i][j],(ll)a.a[i][k]*b.a[k][j]%Mod);
		res.n=I,res.m=J;
		return res;
	}
	friend Matrix operator^(Matrix a,int k)
	{
		Matrix res;
		res.n=res.m=2;
		res.a[1][1]=res.a[2][2]=1;
		for(;k;k>>=1,a=a*a) (k&1)&&(res=res*a,1);
		return res;
	}
	inline void print()
	{
		write(n,' ',m,'\n');
		for(int i=1;i<=n;++i,puts(""))
			for(int j=1;j<=m;++j) write(a[i][j],' ');
	}
}Init,I1,I2,ans;
inline void init()
{
	Init.n=1,Init.m=2;
	Init.a[1][1]=Init.a[1][2]=1;
	I1.n=I1.m=I2.n=I2.m=2;
	I1.a[1][1]=A,I1.a[1][2]=0,I1.a[2][1]=B,I1.a[2][2]=1;
	I2.a[1][1]=C,I2.a[1][2]=0,I2.a[2][1]=D,I2.a[2][2]=1;
}
inline void readIn(char *s,int &x,int p)
{
	int len=std::strlen(s+1);
	for(int i=1;i<=len;++i) x=(((ll)x*10+s[i]-'0')%p+p)%p;
}
char StrN[MAXN],StrM[MAXN];
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	scanf("%s%s",StrN+1,StrM+1);	 
	read(A,B,C,D);pM=Mod2+(A==1);
	readIn(StrM,M,pM);
	init();
	Matrix I3=I1;
	I1=I1^(((M-1)+pM)%pM);I1=I1*I2;
	if(I1.a[1][1]==1) pN=Mod;
	else pN=Mod2;
	readIn(StrN,N,pN);
	I1=I1^(((N-1)+pN)%pN);Init=Init*I1;
	I3=I3^(((M-1)+pM)%pM);Init=Init*I3;
	write(Init.a[1][1]);
	return 0;
}
/*

*/

Remainders Game

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/contest/687/problem/B

形式化题意：有个数，问对于所有正整数，如果知道所有的，是否可以唯一确定的值。

数据范围：

考虑把题目换一种形式，已知：

$\begin{cases} x&\equiv b_1\pmod{c_1}\\ x&\equiv b_2\pmod{c_2}\\ &\cdots\\ x&\equiv b_n\pmod{c_n} \end{cases}$

求是否存在唯一解，有。

但发现这样也是不好做的，但我们可以借助这个形式，因为在的最后，我们等价于求得一个，如果我们能保证唯一，那就意味着我们可以唯一确定所有的。

那显然地，如果的话，我们也就可以唯一确定了。

注意最后的可能巨大，所以要提前取模。

AC Code

// ----- Eternally question-----
// Problem: B. Remainders Game
// Contest: Codeforces - Codeforces Round 360 (Div. 1)
// URL: https://codeforces.com/problemset/problem/687/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-28 20:00:22
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
ll N,K,Lcm;
ll gcd(ll a,ll b){ return !b?a:gcd(b,a%b); }
inline ll lcm(ll a,ll b){ return (ll)a*b/gcd(a,b); }
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,K);
	Lcm=1;
	for(int i=1;i<=N;++i)
	{
		ll c;read(c);
		if(!Lcm) continue;
		Lcm=lcm(Lcm,c);
		Lcm%=K;
	}
	puts(!Lcm?"Yes":"No");
	return 0;
}
/*

*/

Power Tower

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/906/D

形式化题意：给定一个长度为的序列，共次询问，每次询问求:

${w_l}^{\left( {w_{l+1}}^{\left({w_{l+2}}^{\left( {w_{l+3}}^{\cdots^{\left({w_r}\right)}} \right)}\right)} \right)}$

也就是求构成的幂塔。对取模。

数据范围：

考虑并没有办法像之前某次那样维护线段树求乘积，第一这里的幂塔是由上至下，所以没法，其二，还要考虑这个不一定是质数。

首先考虑欧拉定理的本质：，这里要求，所以并不一定适用，所以我们考虑使用扩展欧拉定理：

$x^n\equiv \begin{cases} x^{n\bmod \varphi(p)+\varphi(p)}&,n\geq\varphi(p)\\ x^n&,n<\varphi(p) \end{cases} \pmod p$

这个过程称作欧拉降幂，可以把指数降到级。

有一个结论，是对于，一定存在，而对于所有，一定有。这意味着我们可以递归处理模数，每递归一层就，这样的话，在不多于层，模数就会成为，此时的任何运算都无意义，可以直接结束递归了。

因为较大，所以我们直接求欧拉函数而非线性筛，存一个哈希表就可以了。

时间复杂度。

AC Code

// ----- Eternally question-----
// Problem: D. Power Tower
// Contest: Codeforces - Codeforces Round 454 (Div. 1, based on Technocup 2018 Elimination Round 4)
// URL: https://codeforces.com/problemset/problem/906/D
// Memory Limit: 256 MB
// Time Limit: 4500 ms
// Written by: Eternity
// Time: 2023-07-29 08:47:50
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
int N,P,Q,a[MAXN],ql,qr;
std::unordered_map<int,int>Phi;
inline int getPhi(int p)
{
	int res=p;
	for(int i=2;i*i<=p;++i)
	{
		if(p%i==0)
		{
			res=res/i*(i-1);
			while(p%i==0) p/=i;
		}
	}
	if(p>1) res=res/p*(p-1);
	return res;
}
inline int Mod(ll x,int p)
{
	if(x>=p) return x%p+p;
	return x;
}
inline int qPow(int a,int b,int p)
{
	int res=1;
	while(b)
	{
		if(b&1) res=Mod((ll)res*a,p);
		a=Mod((ll)a*a,p);b>>=1;
	}
	return res;
}
int dfs(int x,int p)
{
	if(x>qr||p==1) return 1;
	if(Phi.find(p)==Phi.end()) Phi[p]=getPhi(p);
	int res=dfs(x+1,Phi[p]);
	return qPow(a[x],res,p);
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,P);
	for(int i=1;i<=N;++i) read(a[i]);
	read(Q);
	while(Q--)
	{
		read(ql,qr);
		write(dfs(ql,P)%P,'\n');
	}
	return 0;
}
/*

*/

Master of Phi

题目简介

题目名称：

题目来源：中国大学生程序设计竞赛-杭州站-重现赛

评测链接：https://acm.hdu.edu.cn/showproblem.php?pid=6265

形式化题意：给定一个数以的形式给出，求：

$\sum_{d\mid n}\varphi(d)\times\frac{n}{d}$

对取模。多测。

数据范围：

因为巨大，所以肯定没法数论分块，但可以考虑卷积，好像是有莫反做法的，但我们这里整一个更简单点的。

注意到，所以的贡献与无关，只需要考虑是否包含即可，所以考虑对进行状压。然后计算贡献。

我们记：

$\begin{align} ans&=\nonumber\sum_{d\mid n}\varphi(d)\times\frac{n}{d}\\&=\nonumber \sum_{d\mid n}\left(d\times \prod_{p_i\mid d}\left(1-\frac{1}{p_i}\right)\right)\times\frac{n}{d} \\&=\nonumber \sum_{d\mid n}\left(\left(d\times \prod_{p_i\mid d}\left(1-\frac{1}{p_i}\right)\right)\times n\times\frac{1}{\displaystyle\prod_{p_i\mid d}p_i}\right) \\&=\nonumber \sum_{d\mid n}\left( n\times \prod_{p_i\mid d}\left(1-\frac{1}{p_i}\right) \right) \\&=\nonumber n\times\sum_{d\mid n}\prod_{p_i\mid d} \left(1-\frac{1}{p_i}\right) \end{align}$

但我们发现枚举离我们的状压还是有一点距离，所以我们考虑继续转化状态。有公式。

我们考虑这个问题的本质，是把的所有质因子一字排开，然后选择其中一部分乘起来求欧拉函数后与未选择的部分相乘，那么实际上，无论如何最后的贡献中都有一个，而变量就是被选择的那一部分离散化后要乘上一个。

这样想就很简单了，考虑每一种的选择方式最后会对，这个很显然，那就是次。

所以，对于每一种选择的方式，答案贡献是，这样下来时间复杂度，但这道题卡常，可以用 lowbit 优化，做到。

AC Code

// ----- Eternally question-----
// Problem: Master of Phi
// Contest: HDOJ
// URL: https://acm.hdu.edu.cn/showproblem.php?pid=6265
// Memory Limit: 32 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-07-29 10:09:45
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=22,MAXS=1<<20|10;
const int Mod=998244353;
int Test,M;
ll N,p[MAXN],q[MAXN],Inv[MAXN];
inline ll qPow(ll a,ll b=Mod-2)
{
	ll res=1;
	for(;b;b>>=1,a=(ll)a*a%Mod) (b&1)&&(res=(ll)res*a%Mod);
	return res;
}
inline int lowbit(int x){ return x&(-x); }
ll Dp[MAXS];
int Lg[MAXS];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	for(int i=2;i<MAXS;++i) Lg[i]=Lg[i>>1]+1;
	while(Test--)
	{
		read(M),N=1;
		for(int i=1;i<=M;++i) read(p[i],q[i]),Inv[i]=qPow(p[i]),N=(ll)N*qPow(p[i],q[i])%Mod;
		ll ans=N;Dp[0]=N;
		for(int s=1;s<(1<<M);++s)
		{
			int x=lowbit(s),pos=Lg[x]+1;
			Dp[s]=Dp[s^x]*(p[pos]-1)%Mod*q[pos]%Mod*Inv[pos]%Mod;
			ans=(ans+Dp[s])%Mod;
		}
		write(ans,'\n');
	}
	return 0;
}
/*

*/

这道题还有特别厉害的狄利克雷卷积的做法。考虑欧拉函数是积性函数，而单位函数也是积性函数，所以可以考虑狄利克雷卷积的形式：

$(f\ast g)(n)=\sum_{d\mid n}f(d)\times g\left(\frac{n}{d}\right)$

我们设

$h(n)=\sum_{d\mid n}\varphi(d)\times \mathrm{id}\left(\frac{n}{d}\right)$

所以有。而同样是积性函数，所以可以得到：

$h(n)=\prod_{i=1}^{m}h({p_i}^{q_i})$

所以我们可以直接求解，得到：

$h(p^n)=\sum_{i=0}^{n}\varphi(p^i)\times\mathrm{id}(p^{n-i})$

根据上面欧拉函数的性质，我们对其进行化简：

$h(p^n)=\sum_{i=0}^{n}(p-1)p^{i-1}\times p^{n-i}$

也就是

$h(p^n)=\sum_{i=0}^{n}(p-1)\times p^{n-1}$

需要注意的是当时上述式子不成立，所以需要把提出来。

$h(p^n)=\varphi(1)\times p^n+\sum_{i=1}^{n}(p-1)p^{n-1}$

最后化简可以得到：

$h(p^n)=p^{n-1}\Big( p+n(p-1) \Big)$

所以最后的答案就是：

$\prod_{i=1}^{m}{p_i}^{q_i-1}\big( p_i+q_i\times(p_i-1) \big)$

时间复杂度，不知道比刚刚那个快多少倍，实现超级简单，所以就不贴代码了。

Border

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/1010/C

形式化题意：给定个十进制数，求有哪些末位为能够通过线性组合而出。

数据范围：

考虑这个末位的贡献方式，实际上就是模意义下的同余系。那现在的不等方程形如：

$\sum_{i=1}^{n}c_ix_i\bmod k$

因为都是级别的，所以肯定没法用同余最短路去做，所以考虑同余系构成的本质，也就是在一个长度为的环上每隔标上一个点，最后统计标记的个数。

显然，对于，第一次重叠的时候是在，反之，能够覆盖的部分肯定就满足了。

所以最后我们对所有统计与比较即可，注意把也要算进去。

AC Code

// ----- Eternally question-----
// Problem: C. Border
// Contest: Codeforces - Codeforces Round 499 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1010/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-29 14:32:41
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
int N,K,gc;
int gcd(int a,int b){ return b==0?a:gcd(b,a%b); }
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,K),gc=K;
	for(int i=1,c;i<=N;++i) read(c),gc=gcd(gc,c);
	write(K/gc,'\n');
	for(int i=0;i*gc<K;++i) write(i*gc%K,' ');
	return 0;
}
/*

*/