根据拓展欧几里得对于同余方程 $ax+by=c$ ,有解的条件是 $(a,b)|c$。
那么对于构造的序列的数，前一个数 $a$ 和后一个数 $b$ ,应该满足 $a*x=b(mod m)$ 即 $ax+my=b$;
建图时，遍历 $0 o m-1$，对于没有标记的数 $i$ ，在 $gcd(i,m)$ 和 $i$ 之间连边。
但是，仅仅如此只是把每个数和其与m的最大公因数相连，还有些情况没有考虑。只要满足 $(a,m)|b$，那么 $a,b$就可以连边。
对于一个点，如果他指向的点也是一个起点的话，那么两部分之间是可以相互连接的。
那么，就可以一组一组地找。
然后是 $DAG$ 图上求最长路，还不太会。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=2e5+5; 4 int nxt[N],dp[N]; 5 vector<int>pic[N]; 6 bool vis[N]; 7 typedef long long ll; 8 int n,m; 9 ll exgcd(ll a,ll b,ll &x,ll &y)//拓展欧几里得 10 { 11 if(!b) 12 { 13 x=1; 14 y=0; 15 return a; 16 } 17 ll res=exgcd(b,a%b,x,y); 18 ll tmp=x; 19 x=y; 20 y=tmp-(a/b)*y; 21 return res; 22 } 23 ll cal(ll a,ll b,ll c) 24 { 25 ll x,y; 26 ll gcd=exgcd(a,b,x,y); 27 if(c%gcd) 28 return -1; 29 x=c/gcd*x; 30 b/=gcd; 31 x=(x%b+b)%b; 32 return x;//最小非负解 33 } 34 void dfs(int p) 35 { 36 if(dp[p]) return; 37 int res=0; 38 for(int i=p*2;i<m;i+=p) 39 { 40 if(pic[i].size()) 41 { 42 dfs(i); 43 if(dp[i]>res)//求最大 44 { 45 res=dp[i]; 46 nxt[p]=i;//存下一个点 47 } 48 } 49 } 50 dp[p]=res+pic[p].size(); 51 } 52 int main() 53 { 54 while(scanf("%d%d",&n,&m)!=EOF) 55 { 56 memset(vis,0,sizeof(vis)); 57 for(int i=0;i<m;i++) 58 pic[i].clear(); 59 memset(dp,0,sizeof(dp)); 60 memset(nxt,0,sizeof(nxt)); 61 int a; 62 for(int i=1;i<=n;i++) 63 { 64 scanf("%d",&a); 65 vis[a]=1; 66 } 67 for(int i=1;i<m;i++) 68 {//建图 69 if(!vis[i]) 70 { 71 int t=__gcd(i,m);//以和m的最小公因数为源点建立边 72 pic[t].push_back(i); 73 } 74 } 75 dfs(1); 76 printf("%d ",dp[1]+(!vis[0])); 77 int u=1,v=1; 78 while(u) 79 {//在路径上求解同余方程 80 for(int i=0;i<pic[u].size();i++) 81 { 82 int t=pic[u][i]; 83 int ans=(int)cal((ll)v,(ll)m,(ll)t); 84 printf("%d ",ans); 85 v=t; 86 } 87 u=nxt[u]; 88 } 89 if(!vis[0]) 90 printf("0 "); 91 } 92 return 0; 93 }