fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4. const int MAX = 1000005;
  5. int p, a, b, c, d, xa, ya, xb, yb;
  6. int nexta[MAX], nextb[MAX];
  7. bool mark[MAX];
  8. void go()
  9. {
  10. 	a = nexta[a];
  11. 	b = nextb[b];
  12. }
  13. int main()
  14. {
  15. 	ios::sync_with_stdio(false);
  16. 	cin >> p >> a >> c >> xa >> ya >> b >> d >> xb >> yb;
  17. 	for (int i = 0; i < p; i++)
  18. 	{
  19. 		nexta[i] = (1LL * i * xa + ya) % p;
  20. 		nextb[i] = (1LL * i * xb + yb) % p;
  21. 	}
  22. 	long long ans = 0;
  23. 	while (a != c && !mark[a])
  24. 	{
  25. 		mark[a] = true;
  26. 		go();
  27. 		ans++;
  28. 	}
  29. 	if (mark[a])
  30. 	{
  31. 		cout << -1 << endl;
  32. 		return 0;
  33. 	}
  34. 	if (b == d)
  35. 	{
  36. 		cout << ans << endl;
  37. 		return 0;
  38. 	}
  39. 	int alen = 0;
  40. 	go();
  41. 	alen++;
  42. 	ans++;
  43. 	memset(mark, false, sizeof(mark));
  44. 	while (a != c && !mark[a])
  45. 	{
  46. 		mark[a] = true;
  47. 		go();
  48. 		ans++;
  49. 		alen++;
  50. 	}
  51. 	if (mark[a])
  52. 	{
  53. 		cout << -1 << endl;
  54. 		return 0;
  55. 	}
  56. 	if (b == d)
  57. 	{
  58. 		cout << ans << endl;
  59. 		return 0;
  60. 	}
  61. 	memset(mark, false, sizeof(mark));
  62. 	while (b != d && !mark[b])
  63. 	{
  64. 		mark[b] = true;
  65. 		go();
  66. 		ans++;
  67. 	}
  68. 	if (mark[b])
  69. 	{
  70. 		cout << -1 << endl;
  71. 		return 0;
  72. 	}
  73. 	if (a == c)
  74. 	{
  75. 		cout << ans << endl;
  76. 		return 0;
  77. 	}
  78. 	int blen = 0;
  79. 	go();
  80. 	blen++;
  81. 	ans++;
  82. 	memset(mark, false, sizeof(mark));
  83. 	while (b != d && !mark[b])
  84. 	{
  85. 		mark[b] = true;
  86. 		go();
  87. 		ans++;
  88. 		blen++;
  89. 	}
  90. 	if (mark[b])
  91. 	{
  92. 		cout << -1 << endl;
  93. 		return 0;
  94. 	}
  95. 	if (a == c)
  96. 	{
  97. 		cout << ans << endl;
  98. 		return 0;
  99. 	}
  100. 	int pos = 0;
  101. 	while (a != c)
  102. 	{
  103. 		a = nexta[a];
  104. 		pos++;
  105. 	}
  106. 	pos = alen - pos;
  107. 	memset(mark, false, sizeof(mark));
  108. 	while (pos != 0 && !mark[pos])
  109. 	{
  110. 		mark[pos] = true;
  111. 		pos = (pos + blen) % alen;
  112. 		ans += blen;
  113. 	}
  114. 	if (mark[pos])
  115. 		cout << -1 << endl;
  116. 	else
  117. 		cout << ans << endl;
  118. 	return 0;
  119. }
  120.  
Success #stdin #stdout 0s 12024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/MvB3Y1
language:
C++14 (gcc 8.3)
created:
8 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!