【题解】洛谷P1516 青蛙的约会

前往：我自己搭建的博客

题目

洛谷P1516青蛙的约会

题解

假设跳了t次以后相遇。列式变形后，解同余方程。

注意：欧几里得算法通常情况下默认参数a,b为正数,同时gcd(a,b)也为正数，所以要将参数转成正数，此处提供两种常用方法。

方法一：同余方程是在模意义下的，取参数在模意义下的最小正数即可。

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll p1,p2,len,s1,s2,x,y; ll exgcd(ll a,ll b) { if(!b) {x=1,y=0; return a;} ll d=exgcd(b,a%b); ll z=x; x=y; y=z-a/b*y; return d; } int main() { scanf("%lld%lld%lld%lld%lld",&p1,&p2,&s1,&s2,&len); ll gcd=exgcd(((s1-s2)%len+len)%len,len),c=p2-p1; if(c%gcd) {printf("Impossible\n"); return 0;} ll ans=(c/gcd*x%(len/gcd)+len/gcd)%(len/gcd); printf("%lld\n",ans); return 0; }

 方法二：对方程ax+by=c的所有参数a,b,c取相反数，等式仍成立，而且解不变。由于y不参与运算，所以b可以不变，对答案无影响。

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll p1,p2,len,s1,s2,x,y; ll exgcd(ll a,ll b) { if(!b) {x=1,y=0; return a;} ll d=exgcd(b,a%b); ll z=x; x=y; y=z-a/b*y; return d; } int main() { scanf("%lld%lld%lld%lld%lld",&p1,&p2,&s1,&s2,&len); ll gcd=exgcd(abs(s1-s2),len),c=p2-p1; if(s1-s2<0) c=-c; if(c%gcd) {printf("Impossible\n"); return 0;} ll ans=(c/gcd*x%(len/gcd)+len/gcd)%(len/gcd); printf("%lld\n",ans); return 0; }

更本质的研究：其实，用欧几里得算法递归求gcd时，即使a,b为负数也是有一定意义的，|gcd(a,b)|=gcd(|a|,|b|),下面有一段不严谨的验证代码。

#include <bits/stdc++.h> using namespace std; const int MOD=23333333; int gcd(int a,int b) {return b?gcd(b,a%b):a;} int main() { int a=1,b=2; while(1) { a=(a+264543)%MOD*5%MOD+666; //乱搞的假随机数 b=(b+87954)%MOD*11%MOD+233; printf("%d %d %d %d %d %d\n",a,b,gcd(a,b),gcd(-a,b),gcd(a,-b),gcd(-a,-b)); if(gcd(a,b)!=abs(gcd(-a,b))||gcd(a,b)!=abs(gcd(a,-b))||gcd(a,b)!=abs(gcd(-a,-b))) break; } return 0; }

 所以，当a,b为负数时，也完全可以求出解。但是在求最小正数解时有一些不同，由于gcd<0,则通解的模数也小于0，直接取模可能是最小正数解，也可能是最大负数解，需要特判。

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll p1,p2,len,s1,s2,x,y; ll exgcd(ll a,ll b) { if(!b) {x=1,y=0; return a;} ll d=exgcd(b,a%b); ll z=x; x=y; y=z-a/b*y; return d; } int main() { scanf("%lld%lld%lld%lld%lld",&p1,&p2,&s1,&s2,&len); ll gcd=exgcd(s1-s2,len),c=p2-p1; if(c%gcd) {printf("Impossible\n"); return 0;} ll ans=(c/gcd*x%(len/gcd)+len/gcd)%(len/gcd); if(ans<0) ans-=len/gcd; printf("%lld\n",ans); return 0; }