b415. 輸出優化練習

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

寫題目不只會遇到算法複雜度問題,還會遇到語法上的瓶頸,了解更深入的作業系統架構、語言特性,了解每一個函數的實作方法,就能把代碼效能發揮到淋淋盡緻。當然,對於代碼轉成執行檔的最佳化技巧也是如此,接下來就來做個基礎題吧。

現在請處理一個偽隨機數計算,輸出前 $m$ 個值。

$x_{i+1} \equiv x_{i}^{2} \mod n$

有興趣的同學,可以查閱 Blum Blum Shub (BBS) Generator 相關隨機數算法。

Sample Input

1
2
3
90 141 5
52 57 5
19 129 5

Sample Output

1
2
3
90 63 21 18 42
52 25 55 4 16
19 103 31 58 10

Solution

手動轉字串,減少函數 printf() 的呼叫,一次將答案吐出來便可以達到加速,由於有一部分時間都花在取模,速度最多提升個兩到三倍。

putchar() 速度也會比 printf() 快一點,但沒有實作 buffer 來得快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h> 

namespace mLocalStream {
inline int readchar() {
const int N = 1048576;
static char buf[N];
static char *p = buf, *end = buf;
if(p == end) {
if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
p = buf;
}
return *p++;
}
inline int ReadInt(int *x) {
static char c, neg;
while((c = readchar()) < '-') {if(c == EOF) return 0;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = readchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
class Print {
public:
static const int N = 1048576;
char buf[N], *p, *end;
Print() {
p = buf, end = buf + N - 1;
}
void printInt(int x, char padding) {
static char stk[16];
int idx = 0;
stk[idx++] = padding;
if (!x)
stk[idx++] = '0';
while (x)
stk[idx++] = x%10 + '0', x /= 10;
while (idx) {
if (p == end) {
*p = '\0';
printf("%s", buf), p = buf;
}
*p = stk[--idx], p++;
}
}
static inline void online_printInt(int x) {
static char ch[16];
static int idx;
idx = 0;
if (x == 0) ch[++idx] = 0;
while (x > 0) ch[++idx] = x % 10, x /= 10;
while (idx)
putchar(ch[idx--]+48);
}
~Print() {
*p = '\0';
printf("%s", buf);
}
} bprint;
}
int main() {
int x0, p, n;
while (scanf("%d %d %d", &x0, &p, &n) == 3) {
for (int i = 0; i < n; i++) {
mLocalStream::bprint.printInt(x0, i == n-1 ? '\n' : ' ');
// mLocalStream::Print::online_printInt(x0);
// putchar(i == n-1 ? '\n' : ' ');
x0 = ((long long) x0 * x0)%p;
}
}
return 0;
}