Pagini recente » Cod sursa (job #1477647) | Cod sursa (job #1211801)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int a[1000005];
int b[1000005];
int c[1000005];
int dad[1000005];
int rang[1000005];
int cul[1000005];
int find(int nod) {
if(dad[nod] == nod) {
return nod;
}
return dad[nod] = find(dad[nod]);
}
void merge(int nod1, int nod2) {
if(rang[nod1] > rang[nod2]) dad[nod2] = nod1;
else dad[nod1] = nod2;
if(rang[nod1] == rang[nod2]) ++rang[nod2];
}
int main()
{
ifstream cin("curcubeu.in");
ofstream cout("curcubeu.out");
int n;
cin >> n >> a[1] >> b[1] >> c[1];
dad[1] = 1;
rang[1] = 1;
for(int 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;
dad[i] = i;
rang[i] = 1;
}
for(int i = n - 1; i >= 1; --i) {
int st, dr;
st = min(a[i], b[i]);
dr = max(a[i], b[i]);
int j = st - 1;
do {
++j;
if(cul[j] == 0)
cul[j] = c[i];
merge(find(j), find(dr) + 1);
} while(dad[j] != j && j < dr);
/*if(cul[st] == 0)
cul[st] = c[i];
int stc = st;
st = nxt[st];
nxt[stc] = nxt[dr];
while(st <= dr) {
cul[st] = c[i];
stc = st;
st = nxt[st];
nxt[stc] = nxt[dr];
}*/
}
for(int i = 1; i < n; ++i)
cout << cul[i] << '\n';
return 0;
}