Advertisement
Guest User

Untitled

a guest
Dec 12th, 2019
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.41 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pt pair<int, int>
  6. #define x first
  7. #define y second
  8. #define what_is(x) cerr << #x << " is " << x << endl;
  9. #define endl '\n'
  10. #define int long long
  11. #define ld long double
  12. random_device rd;
  13. mt19937 rnd(rd());
  14. const int inf = __LONG_LONG_MAX__;
  15.  
  16. inline int readInt()
  17. {
  18. int s = 1, x = 0, c = getc(stdin);
  19. while (c <= 32)
  20. c = getc(stdin);
  21. if (c == '-')
  22. s = -1, c = getc(stdin);
  23. while ('0' <= c && c <= '9')
  24. x = x * 10 + c - '0', c = getc(stdin);
  25. return x * s;
  26. }
  27.  
  28. inline void writeInt( int x )
  29. {
  30. char s[20];
  31. int n = 0;
  32. while (x || !n)
  33. s[n++] = '0' + x % 10, x /= 10;
  34. while (n--)
  35. putc(s[n], stdout);
  36. }
  37.  
  38.  
  39.  
  40. bool operator < (const pt &a, const pt &b)
  41. {
  42. return a.x * b.y < b.x * a.y;
  43. }
  44.  
  45. pt mn, mx;
  46. int n, N, ax[200001], ay[200001];
  47.  
  48. inline bool help(const pt &a, const pt &b)
  49. {
  50. return a.x * b.y == a.y * b.x || a < b;
  51. }
  52.  
  53. inline int check(int l, int m)
  54. {
  55. for (int y = max(m - 5000, l); y <= m; ++y)
  56. {
  57. int x = ceil((ld)mn.x * y / mn.y);
  58. if (help({x, y}, mn)) ++x;
  59. while (__gcd(x, y) > 1 && pt(x, y) < mx) ++x;
  60. pt temp = {x, y};
  61. if (mn < temp && temp < mx && x <= N && y <= N) return y;
  62. }
  63.  
  64. return 0;
  65. }
  66.  
  67. inline int getleft(int l)
  68. {
  69. int r = N;
  70. while (r - l > 1)
  71. {
  72. int m = (l + r) / 2, temp = 0, fl = 0;
  73. for (int i = 0; i < 30; ++i)
  74. {
  75. temp = rnd() % (m - l + 2) + l;
  76. if (check(l, temp))
  77. {
  78. fl = 1;
  79. temp = check(l + 1, temp);
  80. break;
  81. }
  82. }
  83.  
  84. if (!fl) temp = check(l + 1, m);
  85. if (temp)
  86. r = temp;
  87. else
  88. l = m;
  89. }
  90.  
  91. return r;
  92. }
  93.  
  94. inline void solve()
  95. {
  96. int y = getleft(0), cnt = 0;
  97. while (y)
  98. {
  99. int x = mn.x * y / mn.y;
  100. for (; x <= N && n && pt(x, y) < mx; ++x)
  101. {
  102. if (__gcd(x, y) > 1 || help(pt(x, y), mn)) continue;
  103. --n;
  104. ax[cnt] = x;
  105. ay[cnt] = y;
  106. ++cnt;
  107. }
  108.  
  109. int prev = y;
  110.  
  111. int temp = check(y + 1, y + 500);
  112. if (temp) y = temp;
  113. else y = getleft(y);
  114.  
  115. if (prev == y) break;
  116. }
  117.  
  118. writeInt(cnt);
  119. putc('\n', stdout);
  120. for (int i = 0; i < cnt; ++i)
  121. {
  122. writeInt(ax[i]);
  123. putc(' ', stdout);
  124. writeInt(ay[i]);
  125. putc('\n', stdout);
  126. }
  127. }
  128.  
  129. signed main()
  130. {
  131. int a, b, c, d;
  132. cin >> a >> b >> c >> d >> N >> n;
  133. mn = {a, b};
  134. mx = {c, d};
  135. int g = __gcd(mn.x, mn.y);
  136. mn.x /= g;
  137. mn.y /= g;
  138.  
  139. g = __gcd(mx.x, mx.y);
  140. mx.x /= g;
  141. mx.y /= g;
  142.  
  143. solve();
  144.  
  145. return 0;
  146. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement