codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

172B.md (2200B)


      1 Source: https://codeforces.com/problemset/problem/172/B
      2 
      3 B. Pseudorandom Sequence Period
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Polycarpus has recently got interested in sequences of pseudorandom numbers. He learned that many programming languages generate such sequences in a similar way: ![](https://espresso.codeforces.com/1505a2bb013efb7ab20b04ab4c345c19fef97ccb.png) (for *i* ≥ 1). Here *a*, *b*, *m* are constants, fixed for the given realization of the pseudorandom numbers generator, *r*0 is the so-called *randseed* (this value can be set from the program using functions like RandSeed(r) or srand(n)), and ![](https://espresso.codeforces.com/e91a39ad64cd7a33e8f1b67cd60e5b40257de950.png) denotes the operation of taking the remainder of division.
     22 
     23 For example, if *a* = 2, *b* = 6, *m* = 12, *r*0 = 11, the generated sequence will be: 4, 2, 10, 2, 10, 2, 10, 2, 10, 2, 10, ....
     24 
     25 Polycarpus realized that any such sequence will sooner or later form a cycle, but the cycle may occur not in the beginning, so there exist a preperiod and a period. The example above shows a preperiod equal to 1 and a period equal to 2.
     26 
     27 Your task is to find the period of a sequence defined by the given values of *a*, *b*, *m* and *r*0. Formally, you have to find such minimum positive integer *t*, for which exists such positive integer *k*, that for any *i* ≥ *k*: *r**i* = *r**i* + *t*.
     28 
     29 Input
     30 
     31 The single line of the input contains four integers *a*, *b*, *m* and *r*0 (1 ≤ *m* ≤ 105, 0 ≤ *a*, *b* ≤ 1000, 0 ≤ *r*0 < *m*), separated by single spaces.
     32 
     33 Output
     34 
     35 Print a single integer — the period of the sequence.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 2 6 12 11
     43 ```
     44 
     45 Output
     46 
     47 ```
     48 2
     49 ```
     50 
     51 Input
     52 
     53 ```
     54 2 3 5 1
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 4
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 3 6 81 9
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 1
     73 ```
     74 
     75 Note
     76 
     77 The first sample is described above.
     78 
     79 In the second sample the sequence is (starting from the first element): 0, 3, 4, 1, 0, 3, 4, 1, 0, ...
     80 
     81 In the third sample the sequence is (starting from the first element): 33, 24, 78, 78, 78, 78, ...