fork download
  1. #include <iostream>
  2. #include <cstdint>
  3.  
  4. template<class T>
  5. T mod(T a, T b)
  6. {
  7. a %= b;
  8. return a>0?a:a+b;
  9. }
  10.  
  11. void ext_euclid(int64_t a, int64_t b, int64_t *lastx, int64_t *lasty)
  12. {
  13. int64_t x = 0;
  14. int64_t y = 1;
  15. *lastx = 1;
  16. *lasty = 0;
  17. int64_t q, r;
  18. int64_t tmp;
  19.  
  20. while (b != 0)
  21. {
  22. q = a / b;
  23. r = a % b;
  24. tmp = x; x = *lastx - q * x; *lastx = tmp;
  25. tmp = y; y = *lasty - q * y; *lasty = tmp;
  26. a = b; b = r;
  27. }
  28. }
  29.  
  30. class ReversibleLCG {
  31. int64_t x;
  32. int64_t a;
  33. int64_t m;
  34. int64_t c;
  35. int64_t ainverse;
  36. public:
  37. ReversibleLCG(int seed) : x(seed), a(1103515245), m(1u<<31u), c(12345)
  38. {
  39. int64_t x, q;
  40. ext_euclid(a, m, &x, &q);
  41. ainverse = mod(x, int64_t(m));
  42. }
  43. unsigned int next()
  44. {
  45. return x = (a*x + c) % m;
  46. }
  47. unsigned int prev()
  48. {
  49. return x= (ainverse*mod(x - c, m)) % m;
  50. }
  51. };
  52.  
  53. int main()
  54. {
  55. ReversibleLCG rng(0);
  56. unsigned int prev = rng.next();
  57. for(int i = 1;i<10;++i)
  58. {
  59. ReversibleLCG rng(i);
  60. unsigned int cur = rng.next();
  61. std::cout << cur-prev << std::endl;
  62. prev = cur;
  63. }
  64. }
Success #stdin #stdout 0s 2852KB
stdin
Standard input is empty
stdout
1103515245
3250998893
1103515245
3250998893
1103515245
3250998893
1103515245
3250998893
1103515245