Pagini recente » Cod sursa (job #1024310) | Cod sursa (job #1394264) | Cod sursa (job #2911739) | Cod sursa (job #1030453) | Cod sursa (job #86015)
Cod sursa(job #86015)
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
#define MAXN 1000005
int N, A, B, C;
vector<int> a, b, c;
int p[MAXN], biggest[MAXN], col[MAXN];
inline int getSet( int x )
{
if (p[x] == x) return x;
return p[x] = getSet( p[x] );
}
inline void unite( int a, int b )
{
a = getSet(a);
b = getSet(b);
if (a == b) return;
if (rand() % 2)
{
p[b] = a;
if (biggest[b] > biggest[a])
biggest[a] = biggest[b];
}
else
{
p[a] = b;
if (biggest[a] > biggest[b])
biggest[b] = biggest[a];
}
}
int main()
{
freopen("curcubeu.in", "rt", stdin);
freopen("curcubeu.out", "wt", stdout);
scanf("%d %d %d %d", &N, &A, &B, &C);
a.reserve(N); b.reserve(N); c.reserve(N);
a.push_back(A); b.push_back(B); c.push_back(C);
for (int i = 2; i <= N - 1; i++)
{
A = (int)(((long long)A * i) % N);
B = (int)(((long long)B * i) % N);
C = (int)(((long long)C * i) % N);
a.push_back(A);
b.push_back(B);
c.push_back(C);
}
for (int k = 1; k < N; k++)
p[k] = k, biggest[k] = k, col[k] = -1;
for (int k = (int)a.size() - 1; k >= 0; k--)
{
int l = min(a[k], b[k]), r = max(a[k], b[k]);
int mother = getSet(l), p = biggest[mother] + 1;
if (col[l] == -1) //mother == l
col[l] = c[k];
for (; p <= r; )
{
if (col[p] == -1)
col[p] = c[k];
unite( mother, p );
mother = getSet(mother);
p = biggest[ mother ] + 1;
}
}
for (int k = 1; k < N; k++)
if (col[k] == -1)
printf("0\n");
else
printf("%d\n", col[k]);
return 0;
}