HDU2669 Romantic 扩展欧几里德 对我来说有陷阱

这道题对我来说有陷阱虽说是赤果果的扩展欧几里德，看样子基本攻还是不够哈，基本功夫一定要好，准备每天上那种洗脑课时分 多看看数论书，弥补一下 自己 狗一样的基础，

这道题用到了一个性质：

对于不定整数方程pa+qb=c，若 c mod Gcd(a, b)=0,则该方程存在整数解，否则不存在整数解。上面已经列出找一个整数解的方法，在找到p * a+q * b = Gcd(a, b)的一组解p0,q0后，/*p * a+q * b = Gcd(a, b)的其他整数解满足：p = p0 + a/Gcd(a, b) * tq = q0 - b/Gcd(a, b) * t(其中t为任意整数)至于pa+qb=c的整数解，只需将p * a+q * b = Gcd(a, b)的每个解乘上 c/Gcd(a, b) 即可在找到p * a+q * b = Gcd(a, b)的一组解p0,q0后，应该是得到p * a+q * b = c的一组解p1 = p0*(c/Gcd(a,b)),q1 = q0*(c/Gcd(a,b))，p * a+q * b = c的其他整数解满足：p = p1 + b/Gcd(a, b) * tq = q1 - a/Gcd(a, b) * t(其中t为任意整数)p 、q就是p * a+q * b = c的所有整数解。就是运用扩展欧几里德求出 的 p，q给的是最小的那一组 有可能是负的 而题目 明显要求了 x不能为负，所以要利用上述性质 来求出最小 正解

#include<iostream>#include<cstdio>#include<list>#include<algorithm>#include<cstring>#include<string>#include<queue>#include<stack>#include<map>#include<vector>#include<cmath>#include<memory.h>#include<set>#define ll long long#define LL __int64#define eps 1e-8const ll INF=9999999999999;#define M 400000100#define inf 0xfffffffusing namespace std;//vector<pair<int,int> > G;//typedef pair<int,int> P;//vector<pair<int,int>> ::iterator iter;////map<ll,int>mp;//map<ll,int>::iterator p;////vector<int>G[30012];LL extgcd(LL a,LL &x,LL b,LL &y){if(b==0){x=1;y=0;return a;}LL r=extgcd(b,x,a%b,y);LL t=x;x=y;y=t-a/b*y;return r;}int main(void){LL a,b;while(cin>>a>>b){LL x0,y0;LL x,y;LL gcd=extgcd(a,x0,b,y0);if(1%gcd!=0){puts("sorry");continue;}x=x0*1/gcd;y=y0*1/gcd;if(x<0){x=x+b/gcd;//就是这里喔，虽然gcd肯定为1，但是为了让自己能尽快的熟练扩展欧几里德，还是坚持写全了y=y-a/gcd;//其实原式子是 x=x+b/gcd*t（t为一个整数，因为运用了循环所以t不用管了）}cout<<x<<" "<<y<<endl;}}