Pagini recente » Cod sursa (job #2617579) | Cod sursa (job #117165) | Cod sursa (job #3290509) | Cod sursa (job #115670) | Cod sursa (job #3124679)
#include <fstream>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
const int N_MAX = 1e7;
const int MAX_BITS = 32;
const int BITS_PER_STEP = 8;
const int BASE = (1 << BITS_PER_STEP);
const int MASK = BASE - 1;
const int NO_BUCKETS = BASE;
int w[N_MAX], v[N_MAX];
int freq[NO_BUCKETS];
void RadixSort(int w[], int v[], int n, int bits) {//LSD
if(bits >= MAX_BITS)
return;
for(int i = 0; i < NO_BUCKETS; ++i)
freq[i] = 0;
for(int i = 0; i < n; ++i)
++freq[(w[i] >> bits) & MASK];
int start = 0, aux;
for(int i = 0; i < NO_BUCKETS; ++i){
aux = freq[i];
freq[i] = start;
start += aux;
}
for(int i = 0; i < n; ++i)
v[freq[(w[i] >> bits) & MASK]++] = w[i];
RadixSort(v, w, n, bits + BITS_PER_STEP);
}
int main() {
int n, b, c;
long long a;
fin >> n >> a >> b >> c;
w[0] = b;
a %= c;
for(int i = 1; i < n; ++i)
w[i] = ((long long) a * w[i - 1] + b) % c;
RadixSort(w, v, n, 0);
for(int i = 0; i < n; i += 10)
fout << w[i] << ' ';
fout.put('\n');
return 0;
}