题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4439
题目大意：给出a，b，S三个数，每次可以选择从a的位置加到b上，也可以从b的位置加到a上，问a或者b的位置上能否达到S。
比如：给出a和b，可以得到的是
(a b)
(a+b b) (a a+b)
(a+2b b) (a+b a+2*b) (2a+b a+b) (a 2a+b)
......
只要符合上面的a和b的系数关系即可。
推了三行，发现了系数x和y只要满足gcd(x,y)==1即可。
然后就RE了，读题不细心：a，b，S的范围是[ 0~10^18 ]。 除了0，导致了RE。
后来就一直WA，为啥呢..........
用的扩展欧几里得求不定方程的解的模板：
LL gcd(LL a,LL b){if(b==0) return a;else return gcd(b,a%b);
}LL ex_gcd(LL a,LL b,LL &x,LL &y){if(b==0){x=1;y=0;return a;}LL r=ex_gcd(b,a%b,x,y);LL t=x;x=y;y=t-a/b*y;return r;
}//求解ax+by=c的解x，y x,y需要提前定义
bool linear_equation(LL a,LL b,LL c,LL &x,LL &y)
{LL d=ex_gcd(a,b,x,y);if(c%d!=0) //即不整除return false;LL k=c/d;x*=k; y*=k; //求得的只是其中一组解，另外的解是：x+b/gcd(a,b)*i y-a/gcd(a,b)*ireturn true;
}
注意最后三行，x=x*c/d。
而最后我要求一个x的最小的值。
用了（x%B+B）% B
所以来说就是（x*c/d）% B 而这个值就是有可能爆LL。所以一直wa。
要变成 x = （x%B）* （c / d %B）
#include<iostream>
#include<stdio.h>
using namespace std;
#define LL long longLL gcd(LL a,LL b){if(b==0) return a;else return gcd(b,a%b);
}LL ex_gcd(LL a,LL b,LL &x,LL &y){if(b==0){x=1;y=0;return a;}LL r=ex_gcd(b,a%b,y,x);y=y-a/b*x;return r;
}//求解ax+by=c的解x，y x,y需要提前定义
bool linear_equation(LL a,LL b,LL c,LL &x,LL &y)
{LL d=ex_gcd(a,b,x,y);if(c%d!=0) //即不整除return false;//LL k=c/d;//x*=k; y*=k; //求得的只是其中一组解，另外的解是：x+b/gcd(a,b)*i y-a/gcd(a,b)*ireturn true;
}int main (){LL a,b,S;while(~scanf("%lld%lld%lld",&a,&b,&S)){if(a==S||b==S) {printf("YES\n");continue;}if(a==0&&b==0) {printf("NO\n");continue;}if(a==0&&S%b==0) {printf("YES\n");continue;}if(a==0&&S%b!=0) {printf("NO\n");continue;}if(b==0&&S%a==0) {printf("YES\n");continue;}if(b==0&&S%a!=0) {printf("NO\n");continue;}int flag = 0;LL x,y;LL i = 1;LL g = gcd(a,b);if(linear_equation(a,b,S,x,y)) {//printf("%lld %lld\n",x,y);LL B = b/g;LL A = a/g;x = (S / g % B) * (x % B);x = (x % B + B) % B;y = (S - (x*a) )/b;while(1){if( y <= 0 ) {break;}if((x>0&&y>0&&gcd(x,y)==1)) {flag = 1; break;}x = x + B;y = y - A;//printf("%lld %lld\n",x,y);}}else{printf("NO\n"); continue;}if(flag==1) printf("YES\n");else printf("NO\n");}return 0;
}
/*
1 2 3
3 4 5
3 4 17
*/
