首页 > 代码库 > uva live 6170
uva live 6170
Esspe-Peasee is an ancient game played by children throughout the land of Acmania. The rules are simple:
A player simply quibs the yorba at the kwonk. If the yorba hurms the kwonk the player gets a foom. If the yorba hurfs the kwonk the player gets a foob.
The objective is to get a twob with as few quibs as possible.
Every group of children has its own opinion regarding the value of a foom, the value of a foob, and the value of a twob. However, everyone agrees that a foob is worth more than a foom, and that a twob is worth more than a foob. You may assume that a foom and a foob can each be represented by a 32 bit integer, and a twob can be represented by a 64 bit integer.
Input
You will be given a number of game instances to solve. Each instance is specified by 3 non-negative integers that represent the value of a foom, a foob and a twob, respectively. The final line contains three 0‘s and should not be processed.
Output
For each instance your program should print `A fooms and B foobs for a twob!‘, on a line by itself as shown in the samples below, where the value of ``A" fooms plus ``B" foobs add up to a twob, and the sum of ``A" and ``B" is as small as possible. ``fooms" and ``foobs" should be appropriately pluralised, as shown in ``Sample Output" below.
If there is no such pair you should print out the age-old chant: `Unquibable!‘
Sample Input
1 6 157 9 227 9 320 9 182 5 90 0 0
Sample Output
3 fooms and 2 foobs for a twob!Unquibable!2 fooms and 2 foobs for a twob!0 fooms and 2 foobs for a twob!2 fooms and 1 foob for a twob!
扩展欧几里得算法不再累赘，网上各种大神讲解。orz
顺便总结一下
ax+by=c 若有解，即c%gcd(a,b)==0，以下均为有解情况：
若c=1 && gcd(a,b)==1
特解 (x0 , y0)
通解 (x0+b*t , y0-a*t)
若c==_c*gcd(a,b)
原方程左右同除gcd(a,b)可简化为 _ax+_by=_c gcd(_a,_b)==1 故转化为上述情况 _ax+_by=1
求得特解为 (x0*_c , y0*_c)
故通解为 (x0*_c+_b*t, y0*_c-_a*t) 即 (x0*c/gcd(a,b)+b/gcd(a,b)*t , y0*c/gcd(a,b)-a/gcd(a,b)*t)
这题值得注意而且经常需要用到的地方，就是x,y>0且保证x+y最小
若需x>0 可直接
x=(x*c%b+b)%b即可找出最小的正数x
y=(c-a*x)/b即可求得对应y
若y<0 则不可能出现x,y同时>0的情况，因为x已经是最小的正数，若减小，则x为负，若增大，则y会减小，y为负
#include <cstdio>#include <cstring>long long a,b,c,d,x,y;long long exgcd(long long a, long long b, long long &x, long long &y){ if(b==0) { x=1; y=0; return a; } long long ret=exgcd(b, a%b, x, y); long long ty=y; y=x-a/b*y; x=ty; return ret;}int main(){ while(scanf("%lld%lld%lld",&a,&b,&c)!=EOF &&(a || b || c)) { long long d=exgcd(a,b,x,y); if(c%d!=0) printf("Unquibable!\n"); else { a=a/d; b=b/d; c=c/d; x=(((x%b)*(c%b)%b)+b)%b;//x刚好大于0 即x的前一个就已经小于0 若使得y小于0 说明无解 y=(c-a*x)/b; if(y<0) { printf("Unquibable!\n"); continue; } if(x==1) { printf("1 foom and "); if(y==1) printf("1 foob for a twob!\n"); else printf("%lld foobs for a twob!\n",y); }else { printf("%lld fooms and ",x); if(y==1) printf("1 foob for a twob!\n"); else printf("%lld foobs for a twob!\n",y); } } } return 0;}