poj1061 青蛙的约会 扩展欧几里德

这道题目还是比较明显的，数据很大很大，用数论来解题大概能想得到

转载一下别人的讲解，转自 http://hi.baidu.com/blackstar08/item/3818e3b3e0b5a9931846973c

本题是很经典的扩展欧几里德的题目，做完本题对扩展欧几里德得就会有一个很清晰的认识了。要解决这个问题，我觉得有几点要比较清楚：1、怎样利用扩展欧几里德得求得一组基本解；2、利用扩展欧几里德求得不定方程的通解；3、保证求出来的解是最小的正整数解。基于以上三个问题，我作如下的总结（以下都是转的知识）：

欧几里德算法

欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：

定理：gcd(a,b) = gcd(b,a mod b)

证明：a可以表示成a = kb + r，则r = a mod b

假设d是a,b的一个公约数，则有

d|a, d|b，而r = a kb，因此d|r

因此d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数，则

d | b , d |r ，但是a = kb +r

因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证.

扩展欧几里德算法

扩展欧几里德算法是用来在已知a, b求解一组p，q使得p * a+q * b = Gcd(a, b) (解一定存在，根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。下面是一个使用C++的实现：

给的模版是我自己用的，个人喜好而已，感觉别人的比较简洁

#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;using namespace std;#define M 400000100#define inf 0xfffffff//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[8000];int mp[1212][1212];int marry[1212];int lx[1212],ly[1212];bool visx[1212],visy[1212];int slack[1212];char tempmp[1212][1212];int dis[2][4]={0,-1,0,1,1,0,-1,0};int n,m;int un,vn;void clear(){un=vn=0;memset(marry,-1,sizeof(marry));/*memset(mp,0,sizeof(mp));*/memset(ly,0,sizeof(ly));for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)mp[i][j]=-inf;}LL exgcd(LL m,LL &x,LL n,LL &y){LL x1,y1,x0,y0;x0=1;y0=0;x1=0;y1=0;LL r=(m%n+n)%n;LL q=(m-r)/n;x=0,y=1;while(r){x=x0-q*x1,y=y0-q*y1;x0=x1,y0=y1;x1=x,y1=y;m=n;n=r;r=m%n;q=(m-r)/n;}return n;}int main(void){LL x,y,m,n,l,ar,br;while(cin>>x>>y>>m>>n>>l){LL temp=exgcd(n-m,ar,l,br);if((x-y)%temp || m==n)puts("Impossible");else{LL ans=l/temp;ar*=(x-y)/temp;ar=(ar%ans+ans)%ans;cout<<ar<<endl;}}}