解題區/解題區 - Zerojudge

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;
}