Poj 1597 – Uniform Generator

題目的意思就是一個生成隨機數的函數，

     Seed[x+1] = （ seed[x] + STEP ） % MOD

其中seed就是我們生成出來的隨機數，至于seed[0]是哪個數并不重要，后面會證明。STEP就是我們每次往前一個所加的值，再module上MOD得到下一個隨機數。

判斷這個隨機生成函數的好壞的依據是如果能夠產生0~MOD-1內的所有數，就是一個好的，否則壞。

我們知道了同余的特性，便可以假設在k步之后，生成的seed[k] = seed[0]，所以由此有

        Seed[k] = （ seed[0] + STEP*k ） % MOD

那么，

        STEP * k = MOD

而我們如果要生產MOD個數，必須使k≥MOD，而且k不可能大于MOD，因為這個條件下生成的數又開始重復，所以k=MOD；在前面的條件下，如果STEP和MOD有大于1的公約數例如d，那么會有STEP*(k/d) = MOD，這就是一個循環了，只會產生k/d<MOD個隨機數。

結論：iff gcd(STEP, MOD) == 1, good choice.