Pagini recente » Cod sursa (job #2502216) | Cod sursa (job #2987402) | Cod sursa (job #2508239) | Cod sursa (job #1391154) | Cod sursa (job #399588)
Cod sursa(job #399588)
#include<stdio.h>
#include<stdlib.h>
#define NMAX 1000004
#define FIN "curcubeu.in"
#define FOUT "curcubeu.out"
#define min(a,b) ((a)<(b)) ? (a) : (b)
#define max(a,b) ((a)>(b)) ? (a) : (b)
using namespace std;
long long a[NMAX],b[NMAX],c[NMAX],n,prev[NMAX],t[NMAX],col[NMAX];
int getP(int x)
{int y,z;
for(y=x;t[y]!=y;y=t[y]);
return y;
}
void unite(int a,int b)
{a=getP(a);b=getP(b);
if(a==b) return;
if(rand()%2)
{t[b]=a;
if(prev[b]>prev[a])
prev[a]=prev[b];
}
else
{t[a]=b;
if(prev[a]>prev[b])
prev[b]=prev[a];
}}
int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%lld %lld %lld %lld",&n,&a[1],&b[1],&c[1]);
for(int i=2;i<n;i++)
{a[i]=(a[i-1]*i)%n;
b[i]=(b[i-1]*i)%n;
c[i]=(c[i-1]*i)%n;
}
for(int i=1;i<n;i++)
{prev[i]=i;
t[i]=i;
col[i]=-1;
}
for(int i=n-1;i>=1;i--)
{
int l=min(a[i],b[i]);int r=max(a[i],b[i]);
int pr=getP(l); int p=prev[pr]+1;
if(col[l]==-1)
{col[l]=c[i];}
for(;p<=r;)
{if(col[p]==-1) col[p]=c[i];
unite(p,pr);
pr=getP(pr);
p=prev[pr]+1;
}
}
for(int i=1;i<=n-1;i++)
if(col[i]==-1) printf("0\n");
else printf("%d\n",col[i]);
return 0;
}