提出 #22302758

---

ソースコード 拡げる

#include <stdio.h>

long long gcd(long long a, long long b, long long *x, long long *y) {
  long long ans = 0;
  long long tmp = 0;
  
  if (a < b) {
    return gcd(b ,a, y, x);
  }
  
  if (b < 2 || a % b == 0) {
    *x = 0;
    *y = 1;
    return b;
  }

  ans = gcd(b, a % b, x, y);
  tmp = *x;
  *x = *y;
  *y = tmp - (a / b) * *y;
  
  return ans;
}

long long main () {
  long long n = 0;
  long long c[3] = {};
  
  int res = 0;
  
  long long trans[3][3] = {};
  long long ans = 10000;
  long long max_c_res[3] = {};
  
  long long gcd_ab = 0;
  long long gcd_abc = 0;
  long long step = 0;
  long long x = 0;
  long long y = 0;
  long long mult_ab = 0;
  long long diff_steps = 0;
  
  long long dummy_x = 0;
  long long dummy_y = 0;
  
  int isFinished = 0;
  
  res = scanf("%lld", &n);
  res = scanf("%lld", c);
  res = scanf("%lld", c+1);
  res = scanf("%lld", c+2);
  
  if (c[1] < c[0]) {
    long long tmp = c[1];
    c[1] = c[0];
    c[0] = tmp;
  }
  
  if (c[2] < c[1]) {
    long long tmp = c[2];
    c[2] = c[1];
    c[1] = tmp;
  }
  
  if (c[1] < c[0]) {
    long long tmp = c[1];
    c[1] = c[0];
    c[0] = tmp;
  }
  
  for (int i = 0; i < 3; i++) {
    for (int j = i; j < 3; j++) {
      long long gcd_ij = gcd(c[i], c[j], &dummy_x, &dummy_y);
      
      trans[i][j] = c[j] / gcd_ij;
      trans[j][i] = c[i] / gcd_ij;
    }
  }
  
  gcd_ab = gcd(c[0], c[1], &x, &y);
  gcd_abc = gcd(gcd_ab, c[2], &mult_ab, max_c_res+2);
  
  if (n % gcd_abc != 0) {
    return 0;
  }
  
  max_c_res[2] *= n / gcd_abc;
  max_c_res[1] = mult_ab * y * (n / gcd_abc);
  max_c_res[0] = mult_ab * x * (n / gcd_abc);
  
  step = gcd_ab / gcd_abc;
  x *= c[2] / gcd_abc;
  y *= c[2] / gcd_abc;
  
  diff_steps = ((n / c[2]) - max_c_res[2]) / step;
  max_c_res[2] += diff_steps * step;
  max_c_res[1] -= diff_steps * y;
  max_c_res[0] -= diff_steps * x;
  
  while(max_c_res[2] >= 0) {
    if (max_c_res[0] < 0) {
      long long k = 1 + (-max_c_res[0] / trans[0][1]);
      max_c_res[0] += k * trans[0][1];
      max_c_res[1] -= k * trans[1][0];
    } else {
      long long k = max_c_res[0] / trans[0][1];
      max_c_res[0] -= k * trans[0][1];
      max_c_res[1] += k * trans[1][0];
    }
    
    if (ans > max_c_res[0] + max_c_res[1] + max_c_res[2]) {
      ans = max_c_res[0] + max_c_res[1] + max_c_res[2];
    }
    
    max_c_res[2] -= step;
    max_c_res[1] += y;
    max_c_res[0] += x;
  }
  
  printf("%lld\n", ans);
  
  return 0;
}

提出情報

ジャッジ結果