// approximsum -- approximate number as sum of integer multiples of two others
// David Eppstein, UC Irvine, 18 Jun 1996

// given a,b,c find x,y >= 0 s.t. ax+by is as close as possible to c
// breaking ties in favor of ax+by<c
//
// in our application (centering text) we will have to do work
// proportional to x+y later, so we can get away with using a simple
// pseudopolynomial algorithm instead of some more complicated
// polynomial integer linear programming algorithm

void approximsum(long a, long b, long c, long & x, long & y)
{
	long i, j;
	i = (c + a - 1)/a;
	j = 0;
	long d = c;
	while (i >= 0) {
		long diff = a*i + b*j - c;
		if (diff > 0) {
			if (d > diff) {
				d = diff;
				x = i;
				y = j;
			}
			i--;
		} else {
			if (d >= -diff) {
				d = -diff;
				x = i;
				y = j;
			}
			j++;
		}
	}
}