Page 4 of 4
Posted: Sat Feb 09, 2008 8:28 pm
by Jan
Use existing thread.
Posted: Sun Feb 10, 2008 7:30 am
by AcmNightivy
Could someone help to find my mistake..i get puzzled..Thanks..And why
gcd (step, mod) == 1 is a Good Choice(found in other thread)..
Posted: Sun Feb 10, 2008 7:52 am
by mf
After each output test set, your program should print exactly one blank line.
AcmNightivy wrote:why
gcd (step, mod) == 1 is a Good Choice(found in other thread)..
That's elementary number theory. Let s=STEP, m=MOD, g=gcd(s,m), the starting seed be x[0], the k-th number of the generated sequence be x[k]: x[k] = (x[0] + s*k) mod m.
Period length is the smallest k>0, such that x[0] = x[k]. Now let's plug formula for x[k] into this equation: x[0] = (x[0] + s*k) mod m. For this equation to hold, m must exactly divide s*k (i.e s*k = 0 mod m).
m divides s*k => (m/g) divides (s/g)*k => k is a multiple of m/g (since m/g and s/g are relatively prime). So the cycle length is m/g, and only when g=1 you get the full cycle.
Posted: Sun Feb 10, 2008 9:21 am
by AcmNightivy
mf~Thank you very much``Though i can't understand the theory clearly..And i know how poor my math is..Thanks``keep hard working~