Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define pt pair<int, int>
- #define x first
- #define y second
- #define what_is(x) cerr << #x << " is " << x << endl;
- #define endl '\n'
- #define int long long
- #define ld long double
- random_device rd;
- mt19937 rnd(rd());
- const int inf = __LONG_LONG_MAX__;
- inline int readInt()
- {
- int s = 1, x = 0, c = getc(stdin);
- while (c <= 32)
- c = getc(stdin);
- if (c == '-')
- s = -1, c = getc(stdin);
- while ('0' <= c && c <= '9')
- x = x * 10 + c - '0', c = getc(stdin);
- return x * s;
- }
- inline void writeInt( int x )
- {
- char s[20];
- int n = 0;
- while (x || !n)
- s[n++] = '0' + x % 10, x /= 10;
- while (n--)
- putc(s[n], stdout);
- }
- bool operator < (const pt &a, const pt &b)
- {
- return a.x * b.y < b.x * a.y;
- }
- pt mn, mx;
- int n, N, ax[200001], ay[200001];
- inline bool help(const pt &a, const pt &b)
- {
- return a.x * b.y == a.y * b.x || a < b;
- }
- inline int check(int l, int m)
- {
- for (int y = max(m - 5000, l); y <= m; ++y)
- {
- int x = ceil((ld)mn.x * y / mn.y);
- if (help({x, y}, mn)) ++x;
- while (__gcd(x, y) > 1 && pt(x, y) < mx) ++x;
- pt temp = {x, y};
- if (mn < temp && temp < mx && x <= N && y <= N) return y;
- }
- return 0;
- }
- inline int getleft(int l)
- {
- int r = N;
- while (r - l > 1)
- {
- int m = (l + r) / 2, temp = 0, fl = 0;
- for (int i = 0; i < 30; ++i)
- {
- temp = rnd() % (m - l + 2) + l;
- if (check(l, temp))
- {
- fl = 1;
- temp = check(l + 1, temp);
- break;
- }
- }
- if (!fl) temp = check(l + 1, m);
- if (temp)
- r = temp;
- else
- l = m;
- }
- return r;
- }
- inline void solve()
- {
- int y = getleft(0), cnt = 0;
- while (y)
- {
- int x = mn.x * y / mn.y;
- for (; x <= N && n && pt(x, y) < mx; ++x)
- {
- if (__gcd(x, y) > 1 || help(pt(x, y), mn)) continue;
- --n;
- ax[cnt] = x;
- ay[cnt] = y;
- ++cnt;
- }
- int prev = y;
- int temp = check(y + 1, y + 500);
- if (temp) y = temp;
- else y = getleft(y);
- if (prev == y) break;
- }
- writeInt(cnt);
- putc('\n', stdout);
- for (int i = 0; i < cnt; ++i)
- {
- writeInt(ax[i]);
- putc(' ', stdout);
- writeInt(ay[i]);
- putc('\n', stdout);
- }
- }
- signed main()
- {
- int a, b, c, d;
- cin >> a >> b >> c >> d >> N >> n;
- mn = {a, b};
- mx = {c, d};
- int g = __gcd(mn.x, mn.y);
- mn.x /= g;
- mn.y /= g;
- g = __gcd(mx.x, mx.y);
- mx.x /= g;
- mx.y /= g;
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement