pku2142.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#define ONLINE

#ifndef ONLINE
#include <time.h>
#endif

int Mod(int a, int b)
{
	if (b == 0)
	{
		return a;
	}
	return a % b;
}

int ABS(int x)
{
	return x > 0 ? x : -x;
}

int E_GCD(int a, int b, int *x, int *y)
{
	int p, x1, y1;
	if (b == 0)
	{
		*x = 1;
		*y = 0;
		return a;
	}
	p = E_GCD(b, a % b, &x1, &y1);
	*x = y1;
	*y = x1 - (a / b) * y1;
	return p;
}

void Solve(int a, int b, int d)
{
	int x, y, nx, ny, ansx, ansy;
	int gcd;
	gcd = E_GCD(a, b, &x, &y);
	a /= gcd;
	b /= gcd;
	d /= gcd;
	nx = Mod(d * x , b);
	if (nx * a < d)
	{
		nx = (nx + 2 * b) % b;
	}
	ny = (a * nx - d) / b;
	ansx = ABS(nx);
	ansy = ABS(ny);
	ny = Mod(d * y , a);
	if (ny * b < d)
	{
		ny = (ny + a * 2) % a;
	}
	nx = (b * ny - d) / a;
	nx = ABS(nx);
	ny = ABS(ny);
	if (nx + ny < ansx + ansy || (nx + ny == ansx + ansy && nx * a + ny * b < ansx * a + ansy * b))
	{
		ansx = nx;
		ansy = ny;
	}
	printf("%d %d\n", ansx, ansy);
}

int main()
{

#ifndef ONLINE
	freopen("PKU2142.in", "r", stdin);
	clock_t start = clock();
#endif
	
	int a, b, d;
	while (EOF != scanf("%d %d %d", &a, &b, &d) && (a + b + d))
	{
		Solve(a, b, d);
	}

#ifndef ONLINE
	printf("TIME:%dms\n", clock() - start);
#endif
	return 0;
}