首页 > 代码库 > 【POJ】【1061】/【BZOJ】【1477】青蛙的约会
【POJ】【1061】/【BZOJ】【1477】青蛙的约会
<style></style>
View Code
扩展欧几里德
根据题意列出不定方程： (x+m*T)-(y+n*T)=k*L; //T表示跳了T次，由于是环，可能追了多圈，所以结果应为k*L
化简得 T(m-n)-kL=y-x;
这就成了我们熟悉的ax+by=c的形式，扩展欧几里得求解T即可（一定要分清哪个是变量x，哪个是常量a）
在研究ax+by==c时，如果c和gcd(a,b)不互质，那么计算出x后需要乘以c/d。
若要让x取得最小正整数解：
T=x*d/b;(这里用的是整数除法（取整）)
x-=T*b/d;
if (x<0) x+=b/d;
1 /************************************************************** 2 Problem: 1477 3 User: Tunix 4 Language: C++ 5 Result: Accepted 6 Time:0 ms 7 Memory:1272 kb 8 ****************************************************************/ 9 10 //BZOJ 147711 #include<cstdio>12 #include<cstring>13 #include<cstdlib>14 #include<iostream>15 #include<algorithm>16 #define rep(i,n) for(int i=0;i<n;++i)17 #define F(i,j,n) for(int i=j;i<=n;++i)18 #define D(i,j,n) for(int i=j;i>=n;--i)19 using namespace std;20 int getint(){21 int v=0,sign=1; char ch=getchar();22 while(ch<‘0‘||ch>‘9‘){ if (ch==‘-‘) sign=-1; ch=getchar();}23 while(ch>=‘0‘&&ch<=‘9‘){ v=v*10+ch-‘0‘; ch=getchar();}24 return v*=sign;25 }26 /******************tamplate*********************/27 typedef long long LL;28 void exgcd(int a,int b,int &d,LL &x,LL &y){29 if (!b) { d=a; x=1; y=0; return; }30 else {exgcd(b,a%b,d,y,x); y-=x*(a/b);}31 }32 int main(){33 int X=getint(), Y=getint(), M=getint(), N=getint(), L=getint();34 int a=M-N,b=L,c=Y-X,d=0;35 LL x,y;36 if (a<0){ a=-a; c=-c; }37 if (c<0){ c=c+L; }38 exgcd(a,b,d,x,y);39 if (c%d || (M==N && X!=Y)) {printf("Impossible\n"); return 0;}40 x*=c/d;41 LL T=x*d/b;// T=x/(b/d)42 x-=T*b/d;43 if (x<0) x+=b/d;44 printf("%lld\n",x);45 return 0;46 }
【POJ】【1061】/【BZOJ】【1477】青蛙的约会
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。