根据拓展欧几里得对于同余方程 $ax+by=c$ ,有解的条件是 $(a,b)|c$。
那么对于构造的序列的数，前一个数 $a$ 和后一个数 $b$ ,应该满足 $a*x=b(mod m)$ 即 $ax+my=b$;
建图时，遍历 $0 \to m-1$，对于没有标记的数 $i$ ，在 $gcd(i,m)$ 和 $i$ 之间连边。
但是，仅仅如此只是把每个数和其与m的最大公因数相连，还有些情况没有考虑。只要满足 $(a,m)|b$，那么 $a,b$就可以连边。
对于一个点，如果他指向的点也是一个起点的话，那么两部分之间是可以相互连接的。
那么，就可以一组一组地找。
然后是 $DAG$ 图上求最长路，还不太会。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+;
int nxt[N],dp[N];
vector<int>pic[N];
bool vis[N];
typedef long long ll;
int n,m;
ll exgcd(ll a,ll b,ll &x,ll &y)//拓展欧几里得
{
if(!b)
{
x=;
y=;
return a;
}
ll res=exgcd(b,a%b,x,y);
ll tmp=x;
x=y;
y=tmp-(a/b)*y;
return res;
}
ll cal(ll a,ll b,ll c)
{
ll x,y;
ll gcd=exgcd(a,b,x,y);
if(c%gcd)
return -;
x=c/gcd*x;
b/=gcd;
x=(x%b+b)%b;
return x;//最小非负解
}
void dfs(int p)
{
if(dp[p]) return;
int res=;
for(int i=p*;i<m;i+=p)
{
if(pic[i].size())
{
dfs(i);
if(dp[i]>res)//求最大
{
res=dp[i];
nxt[p]=i;//存下一个点
}
}
}
dp[p]=res+pic[p].size();
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(vis,,sizeof(vis));
for(int i=;i<m;i++)
pic[i].clear();
memset(dp,,sizeof(dp));
memset(nxt,,sizeof(nxt));
int a;
for(int i=;i<=n;i++)
{
scanf("%d",&a);
vis[a]=;
}
for(int i=;i<m;i++)
{//建图
if(!vis[i])
{
int t=__gcd(i,m);//以和m的最小公因数为源点建立边
pic[t].push_back(i);
}
}
dfs();
printf("%d\n",dp[]+(!vis[]));
int u=,v=;
while(u)
{//在路径上求解同余方程
for(int i=;i<pic[u].size();i++)
{
int t=pic[u][i];
int ans=(int)cal((ll)v,(ll)m,(ll)t);
printf("%d\n",ans);
v=t;
}
u=nxt[u];
}
if(!vis[])
printf("0\n");
}
return ;
}