Poj 1597 – Uniform Generator

題目的意思就是一個(gè)生成隨機(jī)數(shù)的函數(shù)，

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

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

判斷這個(gè)隨機(jī)生成函數(shù)的好壞的依據(jù)是如果能夠產(chǎn)生0~MOD-1內(nèi)的所有數(shù)，就是一個(gè)好的，否則壞。

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

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

那么，

        STEP * k = MOD

而我們?nèi)绻a(chǎn)MOD個(gè)數(shù)，必須使k≥MOD，而且k不可能大于MOD，因?yàn)檫@個(gè)條件下生成的數(shù)又開始重復(fù)，所以k=MOD；在前面的條件下，如果STEP和MOD有大于1的公約數(shù)例如d，那么會(huì)有STEP*(k/d) = MOD，這就是一個(gè)循環(huán)了，只會(huì)產(chǎn)生k/d<MOD個(gè)隨機(jī)數(shù)。

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