Cod sursa(job #2014606)

Utilizator Rodik_RodyRodica Vasilescu Rodik_Rody Data 24 august 2017 01:19:29
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 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;
}