Advertisement
ivnikkk

Untitled

Jan 11th, 2023
760
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.08 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4. #define all(a) a.begin(), a.end()
  5. #define int long long
  6. pair<int, int> gcd_ext(int a, int b, int c) {
  7.     if (a == 0) {
  8.         return { 0ll, c / b };
  9.     }
  10.     auto [x0, y0] = gcd_ext(b % a, a, c);
  11.     int y1 = x0;
  12.     int x1 = y0 - x0 * (b / a);
  13.     return { x1, y1 };
  14. }
  15. int gcd(int a, int b) {
  16.     if (a == 0 || b == 0) {
  17.         return a + b;
  18.     }
  19.     return gcd(b % a, a);
  20. }
  21. int best = 0;
  22. int ans[3] = {};
  23. bool solve(int a, int b, int c, int mn, int n, int ban) {
  24.     int g = gcd(a, b);
  25.     bool sign = c < 0;
  26.     c = abs(c);
  27.     c = (c / g) * g;
  28.     if (sign) {
  29.         c *= -1;
  30.     }
  31.     if (c % g != 0) {
  32.         return false;
  33.     }
  34.     auto [x0, y0] = gcd_ext(a, b, c);
  35.     bool rs = false;
  36.     auto try_update = [&](int x1, int y1) {
  37.         if (mn + x1 > 0 && mn + y1 > 0) {
  38.             if (best < mn * (mn + x1) * (mn + y1)) {
  39.                 best = mn * (mn + x1) * (mn + y1);
  40.                 int arr[2] = { mn + x1, mn + y1 };
  41.                 int it = 0;
  42.                 ans[ban] = mn;
  43.                 for (int i = 0; i < 3; i++) {
  44.                     if (i == ban) { continue; }
  45.                     ans[i] = arr[it++];
  46.                 }
  47.             }
  48.             rs = true;
  49.         }
  50.     };
  51.     {
  52.         int k = b / g;
  53.         int xm = (x0 % k + k) % k;
  54.         int ym = (c - xm * a) / b;
  55.         assert(xm * a + ym * b == c);
  56.         try_update(xm, ym);
  57.         int tl = 0, tr = 1e9 + 1;
  58.         while (tr - tl > 70) {
  59.             int tm = (tr + tl) / 2;
  60.             int x1 = (xm + k * tm);
  61.             int y1 = (c - x1 * a) / b;
  62.             if (y1 > 0) {
  63.                 tl = tm;
  64.             }
  65.             else {
  66.                 tr = tm;
  67.             }
  68.         }
  69.         for (int i = tl; i <= tr; i++) {
  70.             int x1 = (xm + k * i);
  71.             int y1 = (c - x1 * a) / b;
  72.             try_update(x1, y1);
  73.             int j = i / 2;
  74.             x1 = (xm + k * j);
  75.             y1 = (c - x1 * a) / b;
  76.             try_update(x1, y1);
  77.         }
  78.     }
  79.     {
  80.         int k = a / g;
  81.        
  82.         int ym = (y0 % k + k) % k;
  83.         int xm = (c - ym * b) / a;
  84.         try_update(xm, ym);
  85.         assert(xm * a + ym * b == c);
  86.         int tl = 0, tr = 1e9 + 1;
  87.         while (tr - tl > 70) {
  88.             int tm = (tr + tl) / 2;
  89.             int y1 = (ym + k * tm);
  90.             int x1 = (c - y1 * b) / a;
  91.             if (x1 > 0) {
  92.                 tl = tm;
  93.             }
  94.             else {
  95.                 tr = tm;
  96.             }
  97.         }
  98.         for (int i = tl; i <= tr; i++) {
  99.             int y1 = (ym + k * i);
  100.             int x1 = (c - y1 * b) / a;
  101.             try_update(x1, y1);
  102.             int j = i / 2;
  103.             y1 = (ym + k * j);
  104.             x1 = (c - y1 * b) / a;
  105.             try_update(x1, y1);
  106.         }
  107.     }
  108.     //cout << x0 << ' ' << (c - x0 * a) / b << '\n';
  109.     return rs;
  110. }
  111. /*
  112. ax + by + cz = n
  113.  
  114. ax + b(x + d1) + c(x + d2) = n
  115.  
  116. b * d1 + c * d2 = (n - ax - bx - cx)
  117.  
  118.  
  119. ax + by = n
  120. (b%a)x + ay = n
  121.  
  122. (b - b/a * a) x + ay = n
  123.  bx + a(y - b/a x) = n
  124.  
  125. */
  126. bool ok(int mn, int a, int b, int c, int n) {
  127.     int l = n - a * mn - b * mn - c * mn;
  128.     bool rs = false;
  129.     if (solve(b, c, l, mn, n, 0)) {
  130.         rs = true;
  131.     }
  132.     if (solve(a, b, l, mn, n, 2)) {
  133.         rs = true;
  134.     }
  135.     if (solve(a, c, l, mn, n, 1)) {
  136.         rs = true;
  137.     }
  138.     return rs;
  139. }
  140. signed main() {
  141. #ifdef _DEBUG
  142.     freopen("input.txt", "r", stdin);
  143.     freopen("output.txt", "w", stdout);
  144. #endif
  145.     ios_base::sync_with_stdio(false);
  146.     cin.tie(nullptr);
  147.    
  148.     int a, b, c, n; cin >> n >> a >> b >> c;
  149.     for (int i = 1; i <= n; i++) {
  150.         if (ok(i, a, b, c, n)) {
  151.  
  152.         }
  153.     }
  154.     cout << ans[0] * a << ' ' << ans[1] * b << ' ' << ans[2] * c;
  155. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement