Timus1430(裴蜀定理应用)
题目：http://acm.timus.ru/problem.aspx?space=1&num=1430
题意：给出a,b，N,找出自然数x,y满足：N-(a*x+b*y)的值最小，如果有多组解是，输出任意一组。
#include <iostream>#include <string.h>#include <stdio.h>using namespace std;void Work(int a,int b,int n){ if(a == 1) { printf("%d 0\n",n); return; } if(b == 1) { printf("0 %d\n",n); return; } if(a == b) { printf("%d 0\n",n/a); return; } bool flag = false; if(a < b) { swap(a,b); flag = true; } int x; int minval = (1<<31)-1; int t = min(n/a,b); for(int i=0;i<=t;i++) { int tmp = (n-a*i)%b; if(minval > tmp) { minval = tmp; x = i; } } if(flag) printf("%d %d\n",(n-a*x)/b,x); else printf("%d %d\n",x,(n-a*x)/b);}int main(){ int a,b,n; while(~scanf("%d%d%d",&a,&b,&n)) { Work(a,b,n); } return 0;}