相关链接
题目传送门:http://codeforces.com/contest/800/problem/C
解题报告
写一写发现前缀积与$m$的$\gcd$是一个递增的关系,依次为倍数
于是我们将$0 \sim m-1$按照与$m$的$\gcd$分类
然后就是在拓扑图上搞一搞$DP$,输出的时候用拓展欧几里得求一发逆元
总的时间复杂度:$O(n \log n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 5000000; const int M = 10000; int n,m,tot,ans,vis[N],id[N],in[M],num[M]; int head[M],nxt[N],to[N],f[M],itr[M]; vector<int> que[M],vout; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } int gcd(int a, int b) { return b? gcd(b, a%b): a; } inline void AddEdge(int u, int v) { static int E = 1; in[u]++; to[++E] = u; nxt[E] = head[v]; head[v] = E; } void solve(int w) { f[w] = que[w].size() + (itr[w]?f[itr[w]]:0); ans = max(ans, f[w]); for (int i=head[w];i;i=nxt[i]) { if (f[w] > f[itr[to[i]]]) itr[to[i]] = w; if (--in[to[i]] == 0) solve(to[i]); } } void exgcd(int a, int b, LL &x, LL &y) { if (b) {exgcd(b, a%b, y, x); y -= a / b * x;} else {x = 1; y = 0;} } inline int REV(int a, int z) { int tmp = gcd(a, m), b; LL x, y; a /= tmp; z /= tmp; b = m / tmp; exgcd(a, b, x, y); return x * z % m; } void print(int w, int v) { for (int i=0;i<=que[w].size()-1;i++) { int nv = que[w][i], rev = REV(v, nv); vout.push_back((rev+m)%m); v = nv; } if (itr[w]) print(itr[w], v); } int main() { n = read(); m = read(); for (int i=1;i<=n;i++) vis[read()] = 1; for (int i=1;i<m;i++) if (!vis[i]) { int tmp = gcd(m, i); if (!id[tmp]) id[tmp] = ++tot, num[tot] = tmp; que[id[tmp]].push_back(i); } for (int i=1;i<=tot;i++) { for (int j=1;j<=tot;j++) { if (num[j] > num[i] && num[j] % num[i] == 0) { AddEdge(i, j); } } } for (int i=1;i<=tot;i++) if (!in[i]) solve(i); for (int i=1;i<=tot;i++) if (f[i] == ans) {print(i, 1); break;} if (!vis[0]) vout.push_back(0); cout<<vout.size()<<endl; for (int i=0;i<=vout.size()-1;i++) printf("%d ",vout[i]); return 0; }