pages:
  • 1
Xm0on SAYS

hi body

i think the answer for 9111 5309 6000 1234 is not right ! some one can tell me whats going on ?

what means the cycle might not being with the seed ?

etinavid SAYS

Hi! the answer for 9111 5309 6000 1234 case is correct ! and about " cycle might not begin with the seed" , i didn't understand it too for the first time. it says that in some test cases , the algorithm (ZxL+I mod M) make some random nums and after a special num , next nums make a cycle of random nums . for example in that case if we get the next random num , it would be 4283 (1234*9111+5309 mod 6000). and if we cout console 9111 5309 6000 4283 , it would print "Case 3: 500" correct answer. so we should just find that special number . and so because that number is the start of cycle and it has the same remainder as the end number of cycle has. so in this case we have ( we had about this in Discrete math (riazi gosaste) in high school)

(9111 X+5309) mod 6000 = (9111 Y +5309) mod 6000 --> 9111 X = 9111 Y (mod 6000) --> 9111(X-Y)=6000*k (k is just a num multiplied by 6000)

--> gcd(great common denominator ) ya Be Mim Mim of 9111 & 6000 is 3 , so (X-Y)=2000;

it means that you should check in a loop that follwing condition for finding special number

(Zx(L-2000)+I )mod M=(Zx(L) +I) mod M

in a general case instead of 2000 we should type

X-Y= M/gcd(M,Z)

excuse me for my excitement for explaining the problem because i used up all hours of night for this problem :))

etinavid SAYS

it says that in some test cases , the algorithm (ZxL+I mod M) make some random nums and after a special num , next nums make a cycle of random nums

for other testcases( in input samples) we exactly are in a cycle of random numbers but for this one we should make some random nums to reach a cycle.