Pagini recente » Cod sursa (job #1942988) | Cod sursa (job #3213650) | Cod sursa (job #2440721) | Cod sursa (job #49717) | Cod sursa (job #87447)
Cod sursa(job #87447)
#include <stdio.h>
#define NMAX 1000100
long p[NMAX];
long rang[NMAX];
long next[NMAX];
long m[NMAX];
long a[NMAX],b[NMAX],c[NMAX];
long n, s;
long min, max;
inline long minn(long a, long b)
{
return a < b ? a : b;
}
inline long maxx(long a, long b)
{
return a > b ? a : b;
}
long HalmaztKeres(long x)
{
long ss;
while (x != p[x])
x=p[x];
ss=x;
while (x != p[x])
{
p[x]=ss;
x=p[x];
}
return p[x];
}
void HalmaztKeszit(long x)
{
p[x]=x;
rang[x]=0;
}
void Osszekapcsol(long x, long y)
{
if (rang[x]>rang[y])
{
p[y]=x;
if (next[x]<next[y]) next[x]=next[y];
}
else
{
p[x]=y;
if (next[y]<next[x]) next[y]=next[x];
}
if (rang[x]==rang[y] && x != y) ++rang[y];
}
void Egyesit(long x, long y)
{
Osszekapcsol(HalmaztKeres(x),HalmaztKeres(y));
}
int main()
{
freopen("curcubeu.in","r",stdin);
freopen("curcubeu.out","w",stdout);
long i, j;
scanf("%ld %ld %ld %ld", &n, &a[1], &b[1], &c[1]);
for (i=2; i<=n-1; ++i)
{
a[i]=(a[i-1]*i)%n;
b[i]=(b[i-1]*i)%n;
c[i]=(c[i-1]*i)%n;
}
for (i=1; i<=n-1; ++i)
{
HalmaztKeszit(i);
next[i]=i;
}
min=minn(a[n-1],b[n-1]);
max=maxx(a[n-1],b[n-1]);
for (i=min; i<=max; ++i)
{
Egyesit(min,i);
m[i]=c[n-1];
}
for (i=n-2; i>=1; --i)
{
min=minn(a[i],b[i]);
max=maxx(a[i],b[i]);
for (j=min; j<=max; ++j)
{
if (m[j])
{
s=HalmaztKeres(j);
j=next[s];
}
else
{
m[j]=c[i];
if (m[j-1])
{
s=HalmaztKeres(j-1);
Egyesit(s,j);
}
if (m[j+1])
{
s=HalmaztKeres(j+1);
Egyesit(s,j);
}
}
}
}
for (i=1; i<=n-1; ++i)
printf("%ld\n", m[i]);
fclose(stdin);
fclose(stdout);
return 0;
}