Cod sursa(job #533547)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 14 februarie 2011 10:47:03
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<stdio.h>
#define Nmax 1000010

int T[Nmax], a[Nmax], sol[Nmax] ; 
int i, n, A, B, C, t, j ;

struct interval { int x,y,c; } q[Nmax] ;

int find ( int x ) 
{
	int R = x , y ;
	
	for( ; R != T[R] ; R = T[R] ) ;
	
	for( ; x != T[x] ; x = T[x] )
	{
		y = T[x] ;
		T[x] = R ;
		x = y ;
	}
	
	return R ;
}

int main()
{
	freopen("curcubeu.in","r",stdin);
	freopen("curcubeu.out","w",stdout);
	
	scanf("%d %d %d %d",&n,&A,&B,&C);
	
	q[1].x = A ; q[1].y = B ; q[1].c = C ;

	for( i = 2 ; i < n ; i++ )
	{
		q[i].x = ( q[i-1].x * i ) % n ;
		q[i].y = ( q[i-1].y * i ) % n ;
		q[i].c = ( q[i-1].c * i ) % n ;
	}
	
	for( i = 1 ; i <= n ; i++ )
	{
		T[i] = i ;
		a[i] = i ;
	}
	
	for( i = n - 1 ; i ; i-- )
	{
		t = find( q[i].x ) ; 
		
		for( j = a[t] ; j <= q[i].y ; j++ )
			if( a[j] == j  )
			{
				sol[j] = q[i].c ; 
				T[j] = t ; 
			}
			else
				j = a[T[j]] ;
		a[t] = j ;	
	}
	
	for( i = 1 ; i < n ; i++ )
		printf("%d\n",sol[i]);
	
	return 0;
}