Pagini recente » Cod sursa (job #1363596) | Cod sursa (job #2528446) | Cod sursa (job #1007617) | Cod sursa (job #9258) | Cod sursa (job #1168582)
#include <cstdio>
#include <cstring>
using namespace std;
#define MAX 1000001
#define DOI16 65536
int v[MAX], w[MAX], n, a, b, c, aux[DOI16], shift;
unsigned mask;
void radix();
void countsort(int source[], int dest[]);
void afis()
{
int i;
for(i=1; i<=n; i+=10)
printf("%d ", v[i]);
printf("\n");
}
int main()
{
int i;
freopen("radixsort.in", "r", stdin);
freopen("radixsort.out", "w", stdout);
scanf("%d%d%d%d", &n, &a, &b, &c);
v[1] = b;
for(i=2; i<=n; i++)
v[i] = (1ll*a*v[i-1]+b)%c;
radix();
afis();
return 0;
}
void countsort(int source[], int dest[]){
int i;
for(i=1; i<=n; i++)
aux[source[i]&mask>>shift]++;
for(i=1; i<DOI16; i++)
aux[i] += aux[i-1];
for(i=n; i>=1; i--)
dest[aux[source[i]&mask>>shift]--] = source[i];
}
void radix()
{
mask = 0x0000ffff; shift = 0;
countsort(v, w);
memset(aux, 0, sizeof(aux));
mask = 0xffff0000; shift = 16;
countsort(w, v);
}