Pagini recente » Cod sursa (job #1766187) | Cod sursa (job #1816356) | Cod sursa (job #811168) | Cod sursa (job #2538371) | Cod sursa (job #2462072)
/*#include <iostream>
#include <fstream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <list>
#include <bitset>
using namespace std;
ifstream in("curcubeu.in");
ofstream out("curcubeu.out");
const int dim = 1000010;
bitset <dim> am_cul;
int n,parent[dim],ans[dim],a[dim],b[dim],c[dim],start[dim],cate[dim];
int Find(int x)
{
if (x == parent[x])
{
return x;
}
return parent[x] = Find(parent[x]);
}
int Next(int x)
{
int rx = Find(x);
return (start[rx] + cate[rx]);
}
void Union(int x,int y)
{
int rx = Find(x);
int ry = Find(y);
parent[rx] = ry;
cate[ry] += cate[rx];
start[ry] = min(start[ry] , start[rx]);
}
int main()
{
int i,j;
in >> n >> a[1] >> b[1] >> c[1];
for (i=1; i<n; i++)
{
parent[i] = i;
cate[i] = 1;
start[i] = i;
}
int a_nou,b_nou,c_nou;
for (i=2; i<=n-1; 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;
}
int st,dr;
int x;
for (i=n-1; i>= 1; i--)
{
st = min(a[i],b[i]);
dr = max(a[i],b[i]);
x = st;
if (am_cul[x] == 1)
{
x = Find(x);
}
while (x <= dr)
{
am_cul[x] = 1;
ans[x] = c[i];
if (x > 1 && am_cul[x-1])
{
Union(x-1,x);
}
if (x < n-1 && am_cul[x+1])
{
Union(x,x+1);
}
x = Next(x);
}
}
for (i=1; i<=n-1; i++)
{
out << ans[i] << "\n";
}
return 0;
}*/
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
const int dim = 1000001;
int n,parent[dim],ans[dim],a[dim],b[dim],c[dim];
int Find(int x)
{
if (x == parent[x])
{
return x;
}
return parent[x] = Find(parent[x]);
}
int main()
{
freopen("curcubeu.in", "r", stdin);
freopen("curcubeu.out", "w", stdout);
int i,j;
scanf("%d %d %d %d", &n, &a[1], &b[1], &c[1]);
for (i=1; i<=n; i++)
{
parent[i] = i;
}
int a_nou,b_nou,c_nou;
for (i=2; i<=n-1; 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;
}
int st,dr;
for (i=n-1; i>= 1; i--)
{
st = min(a[i],b[i]);
dr = max(a[i],b[i]);
for (j=Find(st); j<=dr; j = Find(j))
{
ans[j] = c[i];
parent[j] = j+1;
}
}
for (i=1; i<=n-1; i++)
{
printf("%d\n", ans[i]);
}
return 0;
}