Pagini recente » Cod sursa (job #2104020) | Cod sursa (job #1400330) | Cod sursa (job #351495) | Cod sursa (job #2942676) | Cod sursa (job #87355)
Cod sursa(job #87355)
//#define DEBUG
#include <cstdio>
#ifdef DEBUG
#include <iostream>
using namespace std;
#endif
#define NMAX 1000005
struct interval{int left,right,color;};
int N,A,B,C;
interval I[NMAX];
int color[NMAX],father[NMAX],next[NMAX];
inline int min(int x, int y)
{
return (x<y)?x:y;
}
inline int max(int x, int y)
{
return (x>y)?x:y;
}
void init()
{
I[1].left=min(A,B);
I[1].right=max(A,B);
I[1].color=C;
for(int i=2; i<N; i++)
{
A = ((long long) A * i) % (long long) N;
B = ((long long) B * i) % (long long) N;
C = ((long long) C * i) % (long long) N;
I[i].left = min(A,B);
I[i].right = max(A,B);
I[i].color = C;
}
#ifdef DEBUG
cerr<<"Intervalele sunt:"<<endl;
for(int i=1; i<N; i++)
cerr<<I[i].left<<"->"<<I[i].right<<"\t\tCul="<<I[i].color<<endl;
cerr<<endl;
#endif
for(int i=1; i<N; i++)
color[i]=0;
for(int i=1; i<=N;i++)
{
father[i]=-1;
next[i]=i+1;
}
}
inline int root(int u)
{
if(father[u]<0)
return u;
else
{
father[u]=root(father[u]);
return father[u];
}
}
inline void join(int u, int v) // u si v sunt 2 radacini
{
if(father[u]<father[v]) // u mai adanc ca v
father[v]=u;
else
if(father[u]>father[v]) // v mai adanc ca u
father[u]=v;
else // aceeasi adancime
{
father[u]=v;
father[v]--;
}
}
void solve()
{
for(int k=N-1; k>=1; --k)
{
int u,v,aux;
u=root(I[k].right);
v=root(I[k].right+1);
if(color[I[k].right+1]==0)
next[u]=I[k].right+1;
else
{
next[u]=next[v];
if(u!=v)
join(u,v);
}
for(int i=I[k].left; i<=I[k].right; )
{
aux=root(i);
if(color[i]==0)
color[i]=I[k].color;
i=next[aux];
next[aux]=next[u];
if(u!=aux)
join(u,aux);
}
}
}
int main()
{
freopen("curcubeu.in","r",stdin);
freopen("curcubeu.out","w",stdout);
scanf("%d %d %d %d",&N,&A,&B,&C);
init();
solve();
for(int i=1; i<N; i++)
printf("%d\n",color[i]);
return 0;
}