Pagini recente » Cod sursa (job #3345937) | Cod sursa (job #3225097) | Cod sursa (job #3306558) | Cod sursa (job #1820649) | Cod sursa (job #3324876)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[1000005];
int b[1000005];
int c[1000005];
int v[1000005];
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");
struct DSU{
int n;
vector <int> t;
vector <int> sz;
vector <int> mx;
DSU() {}
void _assign(int _n) {
n = _n;
for (int i = 0; i < n; i++) {
t.push_back(i);
mx.push_back(i);
}
sz.resize(n, 1);
}
int findr(int x) {
int r = x;
while (r != t[r]) r = t[r];
while (x != r) {
int y = t[x];
t[x] = r;
x = y;
}
return r;
}
int dsu(int x, int y) {
int rx = findr(x), ry = findr(y);
if (rx == ry) return 0;
if (sz[rx] < sz[ry]) swap(rx, ry);
t[ry] = rx;
sz[rx] += sz[ry];
mx[rx] = max(mx[rx], mx[ry]);
return 1;
}
};
DSU dsu;
int main()
{
int n, i, t, d;
fin >> n >> a[1] >> b[1] >> c[1];
for (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;
}
dsu._assign(n + 5);
for (i = n - 1; i >= 1; i--) {
int st = min(a[i], b[i]);
if (!st) st++;
int dr = max(a[i], b[i]);
int last = -1;
for (int j = st; j <= dr; j++) {
if (dsu.findr(j) == j) v[j] = c[i];
if (last != -1) dsu.dsu(j, last);
j = dsu.mx[dsu.findr(j)];
last = j;
}
}
for (i = 1; i < n; i++) fout << v[i] << "\n";
return 0;
}