Pagini recente » Cod sursa (job #2432932) | Cod sursa (job #1602121) | Cod sursa (job #2439711) | Cod sursa (job #2271826) | Cod sursa (job #1681908)
#include <fstream>
#include <stdio.h>
#include <algorithm>
#define h 100000
using namespace std;
int n,i,b[10000001],c[100010],k,x,y,z,a[10000001],t;
long long aux;
char r[20000001];
void in(int n)
{
int k,aux;
long long inv=1;
aux=n;
while (aux>0)
{
k=aux%10;
aux/=10;
inv=inv*10+k;
}
while (inv>9)
{
k=inv%10;
inv/=10;
r[++t]=(char)(k+'0');
}
r[++t]=' ';
}
int main()
{
ifstream fin ("radixsort.in");
freopen ("radixsort.out","w",stdout);
fin>>n>>x>>y>>z;
a[1]=y; t=-1;
for (i=1;i<=n;i++)
{
aux=(x*(long long)a[i-1])%z;
aux=(aux+y)%z;
a[i]=aux;
}
for (i=1;i<=n;i++) c[a[i]%h]++; //bucket 1 - ultimele 5 cifre
for (i=1;i<h;i++) c[i]+=c[i-1];
for (i=n;i>=1;i--)
{
b[c[a[i]%h]]=a[i];
c[a[i]%h]--;
}
for (i=1;i<=h;i++) c[i]=0;
for (i=1;i<=n;i++) c[b[i]/h]++; //bucket 2 - primele 5 cifre
for (i=1;i<h;i++) c[i]+=c[i-1];
for (i=n;i>=1;i--)
{
a[c[b[i]/h]]=b[i];
c[b[i]/h]--;
}
for (i=1;i<=n;i++)
if (i%10==1) in(a[i]);
fwrite(r,t,sizeof(char),stdout);
return 0;
}