Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include "bits/stdc++.h"
- using namespace std;
- #define all(a) a.begin(), a.end()
- #define int long long
- pair<int, int> gcd_ext(int a, int b, int c) {
- if (a == 0) {
- return { 0ll, c / b };
- }
- auto [x0, y0] = gcd_ext(b % a, a, c);
- int y1 = x0;
- int x1 = y0 - x0 * (b / a);
- return { x1, y1 };
- }
- int gcd(int a, int b) {
- if (a == 0 || b == 0) {
- return a + b;
- }
- return gcd(b % a, a);
- }
- int best = 0;
- int ans[3] = {};
- bool solve(int a, int b, int c, int mn, int n, int ban) {
- int g = gcd(a, b);
- bool sign = c < 0;
- c = abs(c);
- c = (c / g) * g;
- if (sign) {
- c *= -1;
- }
- if (c % g != 0) {
- return false;
- }
- auto [x0, y0] = gcd_ext(a, b, c);
- bool rs = false;
- auto try_update = [&](int x1, int y1) {
- if (mn + x1 > 0 && mn + y1 > 0) {
- if (best < mn * (mn + x1) * (mn + y1)) {
- best = mn * (mn + x1) * (mn + y1);
- int arr[2] = { mn + x1, mn + y1 };
- int it = 0;
- ans[ban] = mn;
- for (int i = 0; i < 3; i++) {
- if (i == ban) { continue; }
- ans[i] = arr[it++];
- }
- }
- rs = true;
- }
- };
- {
- int k = b / g;
- int xm = (x0 % k + k) % k;
- int ym = (c - xm * a) / b;
- assert(xm * a + ym * b == c);
- try_update(xm, ym);
- int tl = 0, tr = 1e9 + 1;
- while (tr - tl > 70) {
- int tm = (tr + tl) / 2;
- int x1 = (xm + k * tm);
- int y1 = (c - x1 * a) / b;
- if (y1 > 0) {
- tl = tm;
- }
- else {
- tr = tm;
- }
- }
- for (int i = tl; i <= tr; i++) {
- int x1 = (xm + k * i);
- int y1 = (c - x1 * a) / b;
- try_update(x1, y1);
- int j = i / 2;
- x1 = (xm + k * j);
- y1 = (c - x1 * a) / b;
- try_update(x1, y1);
- }
- }
- {
- int k = a / g;
- int ym = (y0 % k + k) % k;
- int xm = (c - ym * b) / a;
- try_update(xm, ym);
- assert(xm * a + ym * b == c);
- int tl = 0, tr = 1e9 + 1;
- while (tr - tl > 70) {
- int tm = (tr + tl) / 2;
- int y1 = (ym + k * tm);
- int x1 = (c - y1 * b) / a;
- if (x1 > 0) {
- tl = tm;
- }
- else {
- tr = tm;
- }
- }
- for (int i = tl; i <= tr; i++) {
- int y1 = (ym + k * i);
- int x1 = (c - y1 * b) / a;
- try_update(x1, y1);
- int j = i / 2;
- y1 = (ym + k * j);
- x1 = (c - y1 * b) / a;
- try_update(x1, y1);
- }
- }
- //cout << x0 << ' ' << (c - x0 * a) / b << '\n';
- return rs;
- }
- /*
- ax + by + cz = n
- ax + b(x + d1) + c(x + d2) = n
- b * d1 + c * d2 = (n - ax - bx - cx)
- ax + by = n
- (b%a)x + ay = n
- (b - b/a * a) x + ay = n
- bx + a(y - b/a x) = n
- */
- bool ok(int mn, int a, int b, int c, int n) {
- int l = n - a * mn - b * mn - c * mn;
- bool rs = false;
- if (solve(b, c, l, mn, n, 0)) {
- rs = true;
- }
- if (solve(a, b, l, mn, n, 2)) {
- rs = true;
- }
- if (solve(a, c, l, mn, n, 1)) {
- rs = true;
- }
- return rs;
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int a, b, c, n; cin >> n >> a >> b >> c;
- for (int i = 1; i <= n; i++) {
- if (ok(i, a, b, c, n)) {
- }
- }
- cout << ans[0] * a << ' ' << ans[1] * b << ' ' << ans[2] * c;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement