Pagini recente » Cod sursa (job #2876115) | Cod sursa (job #555711) | Cod sursa (job #1624820) | Cod sursa (job #2328639) | Cod sursa (job #2001413)
#include<bits/stdc++.h>
using namespace std;
ifstream in("radixsort.in");
ofstream out("radixsort.out");
const int NMAX = 10000005;
int v[NMAX],aux[NMAX],N,A,B,C;
void read()
{
in>>N>>A>>B>>C;
v[1] = B;
for(int i = 2 ; i <= N ; ++i)
v[i] = (A*v[i-1] + B)%C;
}
void countSort(int digit)
{
int f[11];
for(int i = 0 ; i <= 9 ; ++i)
f[i] = 0;
for(int i = 1 ; i <= N ; ++i)
f[(v[i]/digit)%10] ++;
for(int i = 1 ; i <= 9 ; ++i)
f[i] += f[i-1];
for(int i = N ; i > 0 ; --i){
aux[f[(v[i]/digit)%10]] = v[i];
f[(v[i]/digit)%10] --;
}
for(int i = 1 ; i <= N ; ++i)
v[i] = aux[i];
}
void radixSort()
{
int maxim = -1;
for(int i = 1 ; i <= N ; ++i)
maxim = max(maxim,v[i]);
for(int p = 1 ; maxim / p > 0 ; p *= 10 )
countSort(p);
}
void afis()
{
for(int i = 1 ; i <= N ; i += 10)
out<<v[i]<<" ";
}
int main()
{
read();
radixSort();
afis();
return 0;
}