Cod sursa(job #2627076)

Utilizator euyoTukanul euyo Data 9 iunie 2020 17:42:07
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <stdio.h>
#include <algorithm>

#define MAXQ 1000000

using namespace std;

int a[MAXQ + 1], b[MAXQ + 1], c[MAXQ + 1];
int urm[MAXQ + 1];
int sol[MAXQ + 1];

static inline int findRoot( int x ) {
  int r, xc = x, k;

  while ( x != urm[x] ) {
	x = urm[x];
  }
  r = x;
  while ( xc != urm[xc] ) {
	k = urm[xc];
	urm[xc] = r;
	xc = k;
  }
  return r;
}
static inline void join( int x, int y ) {
  urm[x] = y;
}

int main() {
  FILE *fin = fopen( "curcubeu.in", "r" );
  FILE *fout = fopen( "curcubeu.out", "w" );
  int n, i, ind, rind;
  
  fscanf( fin, "%d%d%d%d", &n, a + 1, b + 1, c + 1 );
  if (a[1] > b[1]) {
	  swap(a[1], b[1]);
  }
  for ( i = 2; i < n; ++i ) {
	a[i] = (a[i - 1] * i) % n;
	b[i] = (b[i - 1] * i) % n;
	c[i] = (c[i - 1] * i) % n;
	urm[i] = i;

	if (a[i] > b[i]) {
		swap(a[i], b[i]);
	}
  }
  for ( i = n - 1; i >= 1; --i ) {
	ind = a[i];
	while ( ind <= b[i] ) {
	  rind = findRoot( ind );
	  join( ind, b[i] );
	  if ( sol[ind] == 0 ) {
		sol[ind] = c[i];
	  }
	  ind = rind + 1;
	}
  }	
  for ( i = 1; i <= n - 1; ++i ) {
	fprintf( fout, "%d\n", sol[i] );
  }
  fclose( fin );
  fclose( fout );
  return 0;
}