Advertisement
Guest User

Untitled

a guest
Oct 20th, 2019
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.01 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5. #define pb push_back
  6. #define X first
  7. #define Y second
  8. #define sz(v) (int)v.size()
  9.  
  10. void solve();
  11.  
  12. main() {
  13. ios_base::sync_with_stdio(0), cin.tie(0);
  14. #ifdef ONPC
  15. freopen("in.txt", "r", stdin);
  16. #endif
  17. int t = 1;
  18. //cin >> t;
  19. while (t--) solve();
  20. return 0;
  21. }
  22.  
  23. ll gcd(ll a, ll b, ll &x, ll &y) {
  24. if (a == 0) {
  25. x = 0;
  26. y = 1;
  27. return b;
  28. }
  29. ll xx, yy;
  30. ll g = gcd(b % a, a, xx, yy);
  31. x = yy - (b / a) * xx;
  32. y = xx;
  33. return g;
  34. }
  35.  
  36. bool find_any(ll a, ll b, ll c, ll &x, ll &y, ll &g) {
  37. g = gcd(a, b, x, y);
  38. if (c % g != 0) return false;
  39. x *= c / g;
  40. y *= c / g;
  41. return true;
  42. }
  43.  
  44. void shift(ll &x, ll &y, ll a, ll b, ll cnt) {
  45. x += cnt * b;
  46. y -= cnt * a;
  47. }
  48.  
  49. ll find_all(ll a, ll b, ll c, ll minx, ll maxx, ll miny, ll maxy) {
  50. ll x, y, g;
  51. if (!find_any(a, b, c, x, y, g)) return 0;
  52. a /= g;
  53. b /= g;
  54. shift(x, y, a, b, (minx - x) / b);
  55. if (x < minx) shift(x, y, a, b, 1);
  56. if (x > maxx) return 0;
  57. ll lx1 = x;
  58. shift(x, y, a, b, (maxx - x) / b);
  59. if (x > maxx) shift(x, y, a, b, -1);
  60. ll rx1 = x;
  61. shift(x, y, a, b, -(miny - y) / a);
  62. if (y < miny) shift(x, y, a, b, -1);
  63. if (y > maxy) return 0;
  64. ll lx2 = x;
  65. shift(x, y, a, b, -(maxy - y) / a);
  66. if (y > maxy) shift(x, y, a, b, 1);
  67. ll rx2 = x;
  68. if (lx2 > rx2) swap(lx2, rx2);
  69. ll lx = max(lx1, lx2);
  70. ll rx = min(rx1, rx2);
  71. return (rx - lx) / b + 1;
  72. }
  73.  
  74.  
  75. ll n, a, b;
  76.  
  77. void solve() {
  78. long long nn, aa, bb;
  79. cin >> nn >> aa >> bb;
  80. n = nn;
  81. a = aa;
  82. b = bb;
  83. ll all = (a + 1) * (b + 1);
  84. ll cur = find_all(2, 3, n, 0, a, 0, b);
  85. ll g = __gcd(all, cur);
  86. if (cur == 0) {
  87. cout << 0;
  88. return;
  89. }
  90. if (cur == all) {
  91. cout << 1;
  92. return;
  93. }
  94. all /= g;
  95. cur /= g;
  96. string s = "";
  97. while (cur) {
  98. s += char(cur % 10 + '0');
  99. cur /= 10;
  100. }
  101. reverse(s.begin(), s.end());
  102. cout << s << '/';
  103. s = "";
  104. while (all) {
  105. s += char('0' + all % 10);
  106. all /= 10;
  107. }
  108. reverse(s.begin(), s.end());
  109. cout << s;
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement