Pagini recente » Cod sursa (job #1470184) | Cod sursa (job #2102507) | Cod sursa (job #2463345) | Cod sursa (job #2483347) | Cod sursa (job #1915207)
#include <cstdio>
#include <algorithm>
using namespace std;
unsigned int N;
unsigned int A[1000000], B[1000000], C[1000000];
unsigned int tree[1000000];
unsigned int start, finish;
unsigned int i, j;
unsigned int sol[1000000];
int main () /// It's a Disjoint-Set Forests' based algorithm.
{
/// READ
freopen("curcubeu.in","r",stdin);
freopen("curcubeu.out","w",stdout);
scanf("%d %d %d %d", &N, &A[1], &B[1], &C[1]);
/// SOLVE
for (i=2; i<=N-1; i++) /// Calculate A, B and C arrays, according to the recurrence formulas.
{
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++) /// Initialize the tree.
tree[i] = 1;
for (i=N-1; i>=1; i--) /// Start the algorithm from the end to the start.
{
start = min(A[i],B[i]); /// Start is the smallest value.
finish = max(A[i],B[i]); /// Finish is the largest value.
while (start <= finish) /// While we have not reached the end of the interval...
if (start == tree[start]) /// If the start node is also its own father...
{
sol[start] = C[i]; /// Solution of index start is the value of C, according to the problem's given information.
tree[start] = finish + 1; /// Update the tree.
}
else /// Else...
{
start = tree[start]; /// We update the start point, so we'll start from it's father.
tree[start] = finish + 1; /// Update the tree.
}
}
/// PRINT TEST
/*
printf("%d\n", N);
for (i=1; i<=N; i++)
printf("%d ", A[i]);
printf("\n");
for (i=1; i<=N; i++)
printf("%d ", B[i]);
printf("\n");
for (i=1; i<=N; i++)
printf("%d ", C[i]);
printf("\n");
for (i=1; i<=N; i++)
printf("%d ", sol[i]);
printf("\n");
*/
/// PRINT
for (i=1; i<=N-1; i++)
printf("%d\n", sol[i]);
return 0;
}