fork download
copy 
  1.  
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <queue>
  6.  
  7. using namespace std;
  8.  
  9. long long x[100001], y[100001];
  10. int t[100001];
  11.  
  12. int gcd(int m, int n) {
  13. 	while (n > 0) {
  14. 		int r = m % n;
  15. 		m = n;
  16. 		n = r;
  17. 	}
  18. 	return m;
  19. }
  20.  
  21. int getPhi(int n) {
  22. 	int res = 1;
  23. 	for (int i = 2; i * i <= n; i ++)
  24. 		if (n % i == 0) {
  25. 			res *= i - 1;
  26. 			n /= i;
  27. 			while (n % i == 0) {
  28. 				res *= i;
  29. 				n /= i;
  30. 			}
  31. 		}
  32. 	if (n > 1) res *= n - 1;
  33. 	return res;
  34. }
  35.  
  36. int getPower(int a, int p, int modulo) {
  37. 	if (p == 0) return 1;
  38. 	int res = getPower(a, p / 2, modulo);
  39. 	res = (long long)res * res % modulo;
  40. 	if (p % 2 == 1) res = (long long)res * a % modulo;
  41. 	return res;
  42. }
  43.  
  44. int main() {
  45. 	int n, a, b;
  46. 	scanf("%d%d%d", &n, &a, &b);
  47. 	for (int i = 0; i < n; i ++) scanf("%d", &t[i]);
  48. 	t[n] = -t[n-1];
  49. 	for (int i = n - 1; i >= 1; i --) t[i] = t[i] - t[i-1];
  50. 	n ++;
  51.  
  52. 	int d = gcd(a, b);
  53. 	for (int i = 0; i < n; i ++) {
  54. 		if (t[i] % d != 0) {
  55. 			printf("-1\n");
  56. 			return 0;
  57. 		}
  58. 		t[i] /= d;
  59. 	}
  60. 	a /= d;
  61. 	b /= d;
  62.  
  63. 	if (a > b) swap(a, b);
  64. 	if (a == 1 && b == 1) {
  65. 		long long ans = 0;
  66. 		for (int i = 0; i < n; i ++) ans += abs(t[i]);
  67. 		printf("%lld\n", ans / 2);
  68. 		return 0;
  69. 	}
  70.  
  71. 	int x0 = getPower(a, getPhi(b) - 1, b);
  72. 	int y0 = (1 - (long long)x0 * a) / b;
  73.  
  74. 	for (int i = 0; i < n; i ++) {
  75. 		x[i] = (long long)x0 * t[i];
  76. 		y[i] = (long long)y0 * t[i];
  77. 		long long head = -t[i], tail = t[i];
  78. 		if (head > tail) swap(head, tail);
  79. 		tail --;
  80. 		while (head <= tail) {
  81. 			long long mid = (head + tail) / 2;
  82. 			long long t1 = abs(x[i] - mid * b) + abs(y[i] + mid * a);
  83. 			long long t2 = abs(x[i] - (mid + 1) * b) + abs(y[i] + (mid + 1) * a);
  84. 			if (t1 < t2) tail = mid - 1; else head = mid + 1;
  85. 		}
  86. 		x[i] -= (tail + 1) * b;
  87. 		y[i] += (tail + 1) * a;
  88. 	}
  89.  
  90. 	long long s = 0;
  91. 	for (int i = 0; i < n; i ++) s += x[i];
  92. 	s /= b;
  93. 	if (s < 0) {
  94. 		swap(a, b);
  95. 		for (int i = 0; i < n; i ++) swap(x[i], y[i]);
  96. 		s *= -1;
  97. 	}
  98.  
  99. 	priority_queue< pair<long long, int> > Q;
  100. 	for (int i = 0; i < n; i ++) {
  101. 		long long tmp = abs(x[i] - b) + abs(y[i] + a) - abs(x[i]) - abs(y[i]);
  102. 		Q.push(make_pair(-tmp, i));
  103. 	}
  104.  
  105. 	for (int i = 0; i < s; i ++) {
  106. 		int loc = Q.top().second;
  107. 		Q.pop();
  108. 		x[loc] -= b;
  109. 		y[loc] += a;
  110. 		long long tmp = abs(x[loc] - b) + abs(y[loc] + a) - abs(x[loc]) - abs(y[loc]);
  111. 		Q.push(make_pair(-tmp, loc));
  112. 	}
  113.  
  114. 	long long ans = 0;
  115. 	for (int i = 0; i < n; i ++) ans += abs(x[i]) + abs(y[i]);
  116. 	printf("%lld\n", ans / 2);
  117.  
  118. 	return 0;
  119. }
  120.  
Success #stdin #stdout 0.02s 4816KB
comments (?)
stdin
copy 
5 2 3
1 2 1 1 -1
stdout
copy 
5
https://ideone.com/BU558
language:
C++ (gcc 8.3)
created:
14 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!