fork download
  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
stdin
0 1 3
903981041 903981051 903981141
stdout
2