Pagini recente » Cod sursa (job #225596) | Cod sursa (job #2293583) | Cod sursa (job #2587178) | Cod sursa (job #1473637) | Cod sursa (job #1905128)
#include <bits/stdc++.h>
using namespace std;
const int kBucket = 1 << 16, kMaxN = 10000000;
inline void fasterLLDivMod(unsigned long long x, unsigned y, unsigned &out_d, unsigned &out_m) {
unsigned xh = (unsigned)(x >> 32), xl = (unsigned)x, d, m;
#ifdef __GNUC__
asm(
"divl %4; \n\t"
: "=a" (d), "=d" (m)
: "d" (xh), "a" (xl), "r" (y)
);
#else
__asm {
mov edx, dword ptr[xh];
mov eax, dword ptr[xl];
div dword ptr[y];
mov dword ptr[d], eax;
mov dword ptr[m], edx;
};
#endif
out_d = d; out_m = m;
}
//x / y < 2^32 !
inline unsigned fasterLLMod(unsigned long long x, unsigned y) {
unsigned dummy, r;
fasterLLDivMod(x, y, dummy, r);
return r;
}
int head[2 * kBucket],
value[kMaxN], to[kMaxN];
char Buff[1 << 17];
int buffPos;
inline void PutChar(const char& ch) {
Buff[buffPos++] = ch;
if(buffPos == (1 << 17)) {
fwrite(Buff, 1, 1 << 17, stdout);
buffPos = 0;
}
}
inline void WriteInteger(int x) {
char digits[10];
int n = 0, q;
do {
q = x / 10;
digits[n++] = x - (q << 1) - (q << 3) + '0';
x = q;
} while (x);
while(n--)
PutChar(digits[n]);
PutChar(' ');
}
int main() {
#ifdef INFOARENA
freopen("radixsort.in", "r", stdin);
freopen("radixsort.out", "w", stdout);
#endif
int n, a, b, c;
scanf("%d%d%d%d", &n, &a, &b, &c);
b %= c;
memset(head, -1, sizeof head);
int x = 0;
for(int i = 0; i < n; ++i) {
x = fasterLLMod(b + 1ULL * x * a, c);
const int where = x & (kBucket - 1);
value[i] = x;
to[i] = head[where];
head[where] = i;
}
for(int i = kBucket - 1; ~i; --i) {
int j = head[i];
while(j != -1) {
const int prev_to = to[j];
const int where = kBucket + (x >> 16);
to[j] = head[where];
head[where] = j;
j = prev_to;
}
}
int counter = 9;
for(int i = 0; i < kBucket; ++i)
for(int x = head[kBucket + i]; x != -1; x = to[x])
if(++counter == 10) {
WriteInteger(value[x]);
counter = 0;
}
fwrite(Buff, 1, buffPos, stdout);
}