Binary search on $X$. For the first subtask, we can check whether the number of gallons of milk that FJ gives is at least $N$ in $O(K)$ time. However, this does not suffice for full points.

How can we do better than $\Theta(K)?$ As the numbers in the statement are up to $10^{12},$ not $10^{18},$ this suggests that some sort of $\sqrt{N}$ factor is involved.

Suppose that we fix $X.$ Then $Y$ decreases over time. It turns out that if we process all transitions that leave $Y$ unchanged in $O(1)$ time, then our solution runs quickly enough! If there are more than $\sqrt {2N}$ distinct values of $Y$ then FJ definitely gives Bessie enough mlik because

It follows that our solution runs in $O(\sqrt N\log N)$ time.

Nick Wu's code:

#include <stdio.h>
 
int valid(long long n, long long k, long long m, long long x) {
  long long g = 0;
  while(k > 0 && g < n) {
    long long y = (n - g) / x;
    if(y < m) {
      long long leftover = (n-g + m-1) / m;
      return leftover <= k;
    }
    long long maxmatch = n - x*y;
    long long numdays = (maxmatch - g) / y + 1;
    if(numdays > k) numdays = k;
    g += y * numdays;
    k -= numdays;
  }
  return g >= n;
}
 
int main() {
  freopen("loan.in", "r", stdin);
  freopen("loan.out", "w", stdout);
  long long n, k, m;
  scanf("%lld %lld %lld", &n, &k, &m);
  long long lhs = 1;
  long long rhs = 1e12;
  while(lhs < rhs) {
    long long mid = (lhs + rhs + 1) / 2;
    if(valid(n, k, m, mid)) {
      lhs = mid;
    }
    else {
      rhs = mid - 1;
    }
  }
  printf("%lld\n", lhs);
}