Pagini recente » Cod sursa (job #774026) | Cod sursa (job #2556164) | Cod sursa (job #1559806) | Cod sursa (job #2310757) | Cod sursa (job #1223061)
#include<cstdio>
#include<vector>
#define NMAX 10000010
#define BYTE 8
using namespace std;
unsigned int V[NMAX];
int N;
void read() {
freopen("radixsort.in", "r", stdin);
freopen("radixsort.out", "w", stdout);
unsigned int A, B, C;
scanf("%d %u %u %u", &N, &A, &B, &C);
V[1] = B % C;
for (int i = 2 ; i <= N ; i++)
V[i] = (1LL * A * V[i - 1] % C + B) % C;
}
unsigned int get_byte(unsigned int val, int byte) {
return (val >> (byte * BYTE)) & ((1<<BYTE) - 1);
}
void count_sort(int c_byte) {
vector<unsigned int> Count[1<<BYTE];
for (int i = 0 ; i < 1<<BYTE ; i++)
Count[i].clear();
for (int i = 1 ; i <= N ; i++)
Count[get_byte(V[i], c_byte)].push_back(V[i]);
for (int i = 0, k = 0 ; i < 1<<BYTE; i++)
for (vector<unsigned int> :: iterator it = Count[i].begin() ; it != Count[i].end() ; it++)
V[++k] = *it;
}
void radix_sort() {
for (int c_byte = 0 ; c_byte <= 3 ; c_byte++)
count_sort(c_byte);
}
void print() {
for (int i = 1 ; i <= N ; i += 10)
printf("%u ", V[i]);
printf("\n");
}
int main() {
read();
radix_sort();
print();
return 0;
}