Cod sursa(job #601415)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 6 iulie 2011 15:02:26
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb

#include <cstdio>
#include <fstream>

using namespace std;

#define N 1000000

int nxt[N],a[N],b[N],c[N],v[N];

int find (int x){
	
	int h=x;
	for(;h!=nxt[h];h=nxt[h]);
	for(int y;x!=h;x=y){
		y=nxt[x];
		nxt[x]=h;
		}
	
	return x;}
	
	void solve (int x,int y){
		
		if(x<y)
			nxt[x]=y;
		else
			nxt[y]=x;
		
		}

int main ()
{
	
	int n;
	ifstream f ("curcubeu.in");
	freopen ("curcubeu.out","w",stdout);
	f>>n>>a[1]>>b[1]>>c[1];
	for(int i=2;i<n;++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]);
		nxt[i]=i;
		}
	nxt[1]=1;
	nxt[n]=n;
	for(int i=n-1;i;--i)
		for(a[i]=find(a[i]);a[i]<=b[i];a[i]=find(a[i])){
			v[a[i]]=c[i];
			solve(find(a[i]),find(a[i]+1));
			}
	for(int i=1;i<n;++i)
		printf("%d\n",v[i]);
	
	return 0;}