Cod sursa(job #728574)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 28 martie 2012 19:59:14
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<cstdio>
#include<algorithm>
#define dim 1000001

using namespace std;
int A[dim],B[dim],C[dim],N,i,j,T[dim],t,a,b,sol[dim];


inline int  tata(int x) {
	int y , r ; 
	y=r=x ;
	for (;r!=T[r];r=T[r]);
	while( x != T[x]   ){ 
		
		t=T[x];
		T[x]=r;
		x=t;
		
	}
	
	return r;
}
inline void uon(int x,int y){

	if(x>y)
		T[y]=x;
	else
		T[x]=y;
}
int main (){
	freopen("curcubeu.in","r",stdin);
	freopen("curcubeu.out","w",stdout);
	
	scanf("%d%d%d%d",&N  , &A[1], &B[1], &C[1]);
		
	if(A[1]>B[1])
		swap( A[1] , B[1] );
	T[1]=1; T[N]=N;
	for(int i=2; i<N ; ++i ){
		T[i]=i;
		A[i]=  (1LL*A[i-1]*i )%N; 
		B[i]= (1LL*B[i-1]*i )%N; 
		C[i]= (1LL*C[i-1]*i )%N;
		if(A[i]>B[i])
			swap( A[i] , B[i] );		
	}
	for(int i=N-1 ; i>=1 ; --i ) {
		
		for(A[i]=tata(A[i]) ; A[i]<=B[i] ; A[i]=tata(A[i])){
			
			sol[A[i]]=C[i];
			uon(tata(A[i]),tata(A[i]+1));
			
		}
	}		
	
	for(int  i=1 ; i<N ; ++i )
		printf("%d\n",sol[i]);
	return 0;
}