Problem Statement
Hermi has read somewhere that one of the measures of quality for a pseudorandom generator is the length of its period. Help him test some simple generators for this property.
Formally, the period length of an infinite sequence { A[0], A[1], A[2], ... } is the smallest positive integer p such that starting from some n=n0 we have A[n+p] = A[n] for all n. Of course, some infinite sequences don't have any period, but those in this problem will all have some finite periods.
Note that the period doesn't have to start right at the beginning of the sequence. For example, suppose we have the sequence { 4, 7, 1024, 15, 1, 2, 3, 1, 2, 3, 1, 2, 3, ... } that goes on by repeating 1, 2, 3 forever. The length of the period of this sequence is 3.
Hermi's generators are linear congruential generators.
You are given the parameters of one generator: the
state = seed
while True:
print(state)
state = (state * a + b) modulo m
Definition
- Class:
- CycleLength
- Method:
- solve
- Parameters:
- int, int, int, int
- Returns:
- int
- Method signature:
- int solve(int seed, int a, int b, int m)
- (be sure your method is public)
Notes
- It can be shown that the output of the generator always has a finite period.
Constraints
- m will be between 1 and 10^6, inclusive.
- seed, a and b will each be between 0 and m-1, inclusive.
Examples
7
3
4
10
Returns: 4
The generated sequence is {7, 5, 9, 1, 7, 5, 9, 1, 7, 5, 9, 1, ...} and its period length is 4.
1
2
0
997
Returns: 332
The sequence begins {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 27, ...}. Eventually it starts repeating itself.
47
0
23
100
Returns: 1
The sequence {47, 23, 23, 23, 23, 23, 23, 23, 23, ...} has period length 1.
548687
538918
376524
931161
Returns: 690
Watch out for integer overflow when generating the sequence! The correct first few elements of this sequence are { 548687, 52352, 564521, 120560, 571829, 653435, 861713, 684494, 565739, 54179, 930530, 193031, ... }
921855
810482
849306
937528
Returns: 58595
970732
585150
156449
979104
Returns: 6
1
2
0
524288
Returns: 1
0
0
0
1
Returns: 1
65562
451082
580533
946117
Returns: 11398
598517
360154
269932
959463
Returns: 6840
405334
411477
645462
967167
Returns: 632
833704
438863
690620
905361
Returns: 147660
107432
656
276621
903101
Returns: 112644
759019
573243
9579
963118
Returns: 5808
595138
448475
241221
941363
Returns: 235329
548687
538918
376524
931161
Returns: 690
253806
34879
588194
957962
Returns: 1545
751548
721002
370621
949042
Returns: 18360
358522
584885
603039
978771
Returns: 54376
205503
250210
826916
999863
Returns: 499931
959398
980978
36992
995571
Returns: 2160
350148
102704
380463
916449
Returns: 152741
402211
532997
566365
975805
Returns: 39032
101815
680324
914300
933139
Returns: 461900
733173
886702
351125
929747
Returns: 300
493910
780328
115496
928646
Returns: 231260
634026
370198
707636
954612
Returns: 26514
921855
810482
849306
937528
Returns: 58595
848416
582238
274296
931323
Returns: 49014
558560
592847
42058
946785
Returns: 1260
327372
590073
817537
963431
Returns: 12512
272885
765681
544629
951836
Returns: 475916
635798
119470
657884
928958
Returns: 464478
398319
508977
265435
927143
Returns: 62730
970732
585150
156449
979104
Returns: 6
15928
178567
573563
958181
Returns: 205323
843403
798459
86796
982202
Returns: 1020
278658
536068
852131
909778
Returns: 454888
573429
499657
820338
981594
Returns: 26070
383336
796056
34793
957096
Returns: 210
277886
942872
675588
979664
Returns: 4373
542078
706855
953674
979774
Returns: 244943
958841
742586
669331
961841
Returns: 96184
869824
23313
604945
941286
Returns: 77082
221631
362769
452604
931853
Returns: 714
192954
185259
492613
990674
Returns: 495336
134088
103198
143298
926040
Returns: 2572
823240
597291
360767
995737
Returns: 47416
411419
113335
279828
969127
Returns: 158304
473
684327
128320
958185
Returns: 20988
70427
387185
21728
954272
Returns: 542
43731
147260
189980
934635
Returns: 14376
536512
876160
514833
996881
Returns: 498440
821122
810416
851118
926364
Returns: 8568
553936
475624
590983
964840
Returns: 24120
10472
728797
77432
974361
Returns: 26190
876371
157881
569842
922953
Returns: 8790
666396
909209
48953
944347
Returns: 117782
548687
548687
548687
548688
Returns: 2
1
1
1
1000000
Returns: 1000000
47
123456
23
999983
Returns: 999982
0
1
1
1000000
Returns: 1000000