NEFU84 五指山扩展欧几里德的应用
解析过程跟上一道很像，http://blog.csdn.net/u010682557/article/details/13612759
设要跳t次，我们列出方程 d*t-np=y-x;(这里的p是一个正整数)
然后开始利用扩展欧几里德来解，我自己写的那个不知道WA在哪里了，后来看了别人的，他们只是 求gcd的值的时候 另外写了个gcd的函数而已，而我顺便在扩展欧几里德时求出gcd的值就是错的，不知道是为什么，我先贴一下WA的代码 有高手路过 知道错哪里了求指点啊，刚开始数论没多久
这个代码一直WA
#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-8//const 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;}ll GCD(ll a,ll b){if(b==0)return a;return GCD(b,a%b);}int main(void){int T;cin>>T;while(T--){ll n,d,x,y;cin>>n>>d>>x>>y;ll dis;dis=(y-x+n)%n;ll t0,p0;ll gcd=GCD(d,n);if(dis%gcd!=0){puts("Impossible");continue;}d/=gcd;n/=gcd;extgcd(d,t0,n,p0);t0=(t0+n)%n;ll t=(t0*dis/gcd+n)%n;cout<<t<<endl;}}