前置知识
简化题意
给定一个长度为 \(n\) 的序列 \(a\)，求能用 \(r=(\sum\limits_{i=1}^{n}d_ia_i) \bmod k\) 表示的不同的 \(r\) 的个数及所有情况，其中对于每一个 \(i(1 \le i \le n)\) 均有 \(d_i\) 为非负整数。
解法
依据裴蜀定理，不难得到存在一个长度为 \(n\) 的序列 \(x\) 满足 \(a_1 x_1+a_2 x_2+a_3 x_3+ \dots = \gcd(a_1,a_2,a_3, \dots ,a_n)\)，其中对于每一个 \(i(1 \le i \le n)\) 均有 \(x_i\) 为整数。所以有 \(\gcd(a_1,a_2,a_3, \dots ,a_n)|\sum\limits_{i=1}^{n}d_ia_i\)。
设 \(d=\gcd(a_1,a_2,a_3, \dots ,a_n),\sum\limits_{i=1}^{n}d_ia_i=dl=kh+r\)，不难得到当 \(h\) 极大时有一组长度为 \(n\) 的序列 \(x\) 满足对于每一个 \(i(1 \le i \le n)\) 均有 \(x_i\) 为非负整数。
- 这里可以感性理解一下。
于是可以建立一个不定方程 \(dl=kh+r\)，用 \(x'\) 代替 \(l\)，用 \(y'\) 代替 \(-h\)，得 \(dx'+ky'=r\)。依据裴蜀定理，该方程有解当且仅当 \(\gcd(d,k)|r\)。所以共能组成 \(\dfrac{r}{\gcd(d,k)}\) 个不同的数，为保证递增有第 \(i(1 \le i \le \dfrac{r}{\gcd(d,k)})\) 个数为 \((i-1) \times \gcd(d,k)\)。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sort stable_sort
#define endl '\n'
int a[500001];
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int main()
{
int n,k,i,ans=0;
cin>>n>>k;
ans=k;
for(i=1;i<=n;i++)
{
cin>>a[i];
ans=gcd(ans,a[i]);
}
cout<<k/ans<<endl;
for(i=0;i<=k/ans-1;i++)
{
cout<<i*ans<<" ";
}
return 0;
}