相关链接
题目传送门: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;
}
If you are going for finest contents like me, just pay a quick visit this web site daily because it offers quality contents, thanks
Hi just wanted to give you a brief heads up and let you
know a few of the images aren’t loading correctly. I’m not sure why but I think its a linking issue.
I’ve tried it in two different browsers and both show the
same results.
Hurrah! In the end I got a webpage from where I know how to truly get useful
facts concerning my study and knowledge.
Hey very interesting blog!
Pretty! This was an extremely wonderful article.
Many thanks for providing this information.
Very nice blog post. I absolutely appreciate this site. Continue the good work!
With havin so much written content do you ever run into any problems of plagorism or copyright violation? My website
has a lot of unique content I’ve either authored myself or outsourced but it seems a lot of it is popping it up all over the internet without my permission. Do you know any methods to help prevent content from being stolen? I’d
certainly appreciate it.
Hi! Would you mind if I share your blog with my zynga group?
There’s a lot of folks that I think would really enjoy your
content. Please let me know. Thanks
Thanks for finally talking about >【Codeforces 800C】Vulnerable Kerbals – Qizy’s Database <Liked it!
Can you tell us more about this? I’d like to find out some additional information.
Touche. Great arguments. Keep up the great work.
I blog frequently and I seriously appreciate your information. This great article has truly peaked my interest.
I am going to take a note of your blog and keep checking
for new information about once a week. I
opted in for your Feed too.
As the admin of this web site is working, no
question very quickly it will be famous, due to its quality
contents.
whoah this blog is wonderful i love reading your articles. Keep up the great work! You know, many people are looking around for this info, you can help them greatly.
It’s nearly impossible to find knowledgeable people in this
particular topic, however, you seem like you know what you’re talking about!
Thanks
I know this if off topic but I’m looking into starting my
own weblog and was curious what all is needed to
get setup? I’m assuming having a blog like yours would cost a pretty penny?
I’m not very web savvy so I’m not 100% sure. Any tips or advice
would be greatly appreciated. Thanks
What’s up to every one, it’s genuinely a fastidious for me to pay a visit this web site, it contains valuable Information.
Hi to all, how is all, I think every one is getting more from this website, and your views are good designed for
new viewers.
I have been surfing online more than three
hours today, yet I never found any interesting article like yours.
It is pretty worth enough for me. In my view, if all web owners
and bloggers made good content as you did, the internet will
be much more useful than ever before.
This article gives clear idea in favor of the new viewers of blogging, that in fact how to do blogging and site-building.
It’s an remarkable paragraph designed for all the online users; they will take benefit from it I am sure.
Hi there friends, how is everything, and what you would like to say regarding this article,
in my view its genuinely remarkable for me.
I like your writing style really loving this internet site.