fork download
copy 
  1. #include <stdio.h>
  2. #include <stdint.h>
  3. #include <unordered_set>
  4. #include <vector>
  5.  
  6. uint32_t f(uint32_t n, uint32_t m) {
  7. 	if (n < 9) {
  8. 		n += m;
  9. 	}
  10. 	uint64_t t = 0;
  11. 	uint32_t a = n % m;
  12. 	for (int i = 31; i >= 0; i--) {
  13. 		t = (t * (a - 1) + 2) % m * t % m;
  14. 		if (a & 1u << i) {
  15. 			t = (t * a + 1) % m;
  16. 		}
  17. 	}
  18. 	return (uint32_t)(t * a % m);
  19. }
  20.  
  21. int main() {
  22. 	const uint32_t m = 1000000000;
  23. 	const uint32_t n = 20200117;
  24. 	std::unordered_set < uint32_t > v_set;
  25. 	std::vector < uint32_t > v_vect;
  26. 	int c0, c1;
  27. 	uint32_t t = n % m;
  28. 	for (int i = 0; ; i++) {
  29. 		if (v_set.find(t) != v_set.end()) {
  30. 			c1 = i;
  31. 			break;
  32. 		}
  33. 		v_set.insert(t);
  34. 		v_vect.push_back(t);
  35. 		t = f(t, m);
  36. 	}
  37. 	for (int i = 0; ; i++) {
  38. 		if (v_vect[i] == t) {
  39. 			c0 = i;
  40. 			break;
  41. 		}
  42. 	}
  43. 	int c = n % (c1 - c0);
  44. 	if (c < c0) {
  45. 		c += c1 - c0;
  46. 	}
  47. 	printf("%u\n", v_vect[c]);
  48. 	return 0;
  49. }
  50.  
Success #stdin #stdout 0.32s 17552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
434459137
https://ideone.com/g1jJJj
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!