Pagini recente » Cod sursa (job #2007709) | Cod sursa (job #576937) | Istoria paginii runda/hc_round7/clasament | Cod sursa (job #2202289) | Cod sursa (job #2521809)
#include <bits/stdc++.h>
#define N 10000005
#define ll long long
using namespace std;
ifstream f ("radixsort.in");
ofstream g ("radixsort.out");
ll n , A , B , C;
ll a[N] , countt[10] , output[N];
void CountSort(ll exp)
{
memset(countt , 0 , sizeof(countt));
memset(output , 0 , sizeof(output));
ll i;
for(i = 1 ; i <= n ; i++)
++countt[ a[i] / exp % 10 ];
for(i = 0 ; i < 10 ; i++)
countt[i] += countt[i - 1];
for(i = n ; i >= 1 ; i--)
{
output[countt[ a[i] / exp % 10 ]] = a[i];
--countt[ a[i] / exp % 10 ];
}
memcpy(a , output , sizeof(output));
}
void RadixSort(ll maxx)
{
ll exp;
for(exp = 1 ; maxx / exp > 0 ; exp *= 10)
CountSort(exp);
}
int main()
{
ll i , maxx = 0;
f >> n >> A >> B >> C;
a[1] = B;
maxx = B;
for(i = 2 ; i <= n ; i++)
{
a[i] = (A * a[i - 1] % C + B) % C;
maxx = max(maxx , a[i]);
}
RadixSort(maxx);
for(i = 1 ; i <= n ; i += 10)
g << a[i] << ' ';
return 0;
}