fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <map>
  6. #include <set>
  7. #include <queue>
  8. #include <deque>
  9. #include <stack>
  10. #include <cmath>
  11. #include <random>
  12. #include <iomanip>
  13. #include <functional>
  14. #include <list>
  15. #include <unordered_map>
  16. #include <sstream>
  17. #include <istream>
  18. #include <iterator>
  19. #include <numeric>
  20. #include <tuple>
  21. #include <cassert>
  22. using namespace std;
  23.  
  24. long long gcd(long long a, long long b)
  25. {
  26. 	return b == 0 ? a : gcd(b, a % b);
  27. }
  28.  
  29. long long intersect_length(long long l0, long long r0, long long l1, long long r1)
  30. {
  31. 	if (l0 > l1)
  32. 	{
  33. 		swap(l0, l1);
  34. 		swap(r0, r1);
  35. 	}
  36.  
  37. 	long long d0 = r0 - l0 + 1;
  38. 	long long d1 = r1 - l1 + 1;
  39.  
  40. 	d0 -= (l1 - l0);
  41. 	d0 = max(0ll, d0);
  42.  
  43. 	return min(d0, d1);
  44. }
  45.  
  46. int main()
  47. {
  48. 	long long l[2], r[2], t[2], d[2];
  49. 	for (int i = 0; i < 2; i++)
  50. 	{
  51. 		cin >> l[i] >> r[i] >> t[i];
  52. 		d[i] = r[i] - l[i] + 1;
  53. 	}
  54.  
  55. 	if (l[0] == l[1] || gcd(t[0], t[1]) == 1)
  56. 	{
  57. 		cout << min(d[0], d[1]);
  58. 		return 0;
  59. 	}
  60.  
  61. 	int steps = 0;
  62. 	long long ans = 0;
  63. 	while (steps < 500000000)
  64. 	{
  65. 		ans = max(ans, intersect_length(l[0], r[0], l[1], r[1]));
  66.  
  67. 		if (l[0] < l[1])
  68. 		{
  69. 			l[0] += t[0];
  70. 			r[0] += t[0];
  71. 		}
  72. 		else if (l[1] < l[0])
  73. 		{
  74. 			l[1] += t[1];
  75. 			r[1] += t[1];
  76. 		}
  77. 		else
  78. 			break;
  79.  
  80. 		steps++;
  81. 	}
  82.  
  83. 	cout << ans;
  84. }
Success #stdin #stdout 0.88s 15232KB
comments (?)
stdin
copy 
0 1 3
903981041 903981051 903981141
stdout
copy 
2
https://ideone.com/HVDFuc
language:
C++14 (gcc 8.3)
created:
6 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!