P1516 青蛙的约会

P1516 青蛙的约会

传送门

好吧,这是一道裸的拓欧,我也不知道为什么要写这篇博客qwq~~~~

下面开始分析:


我们设总共跳T次可以相遇:

则 A坐标:X+MT; B坐标:Y+NT

那么可以得出:

相遇的充要条件为:(X+MT)-(Y+NT)=PL //P是整数,PL是纬线长度的P倍

变形为:(N-M)* T + L * P=X-Y//T为所求

如果变形成那样还没看出来,那么变成这样总能看出来了吧:(M-N)* T$\equiv$ ≡ (Y-X)(mod L)(注意这个地方有变号,即N-M被我设作M-N,为的是让等式右边冠正号)

没错,它就是个一次同余方程,而我们要做的就是求出它的最小正整数解qwq(特别注意,是正整数,这里有个小坑,后面会讲)

那这就简单了,我们可以通过扩展欧几里德算法求出一组特解,然后对于这组特解,我们再推导出最小解来。

直接套上求最小值代码即可:

x1=(x*(a/d)+l/d)%(l/d);//计算第一个解 
cout<<(x1+(l/d))%(l/d);	

拓展欧几里得算法应该再熟悉不过了吧

int exgcd(long long a,long long b,long long &x, long long &y)
{
   if(b==0)
   {
       x=1;
       y=0;
       return a;
   }
   d=exgcd(b,a%b,x,y);
   long long t=x;
   x=y;
   y=t-a/b*y;
   return d;
}

然后就信心满满的交上去了,结果发现只获得了70分,怎么回事?

因为gcd只对非负整数有意义,所以如果a<0等式两边要同时取负。

    ll a=x-y;
    ll b=n-m;
    if(b<0)
    {
        b=-b;
        a=-a;
    }

最后放上我的AC代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll m,n,x,y,l;
ll d;
int exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    d=exgcd(b,a%b,x,y);
    ll temp=x;
    x=y;
    y=temp-a/b*y;
    return d;
}
int main()
{
    cin>>x>>y>>m>>n>>l;
    ll a=x-y;
    ll b=n-m;
    if(b<0)
    {
        b=-b;
        a=-a;
    }
    exgcd(b,l,x,y);
    if(a%d)
        printf("Impossible");
    else
        {
            int x1=(x*(a/d)+(l/d))%(l/d);//计算第一个解 
	    printf("%d ",(x1+(l/d))%(l/d));	
        }
    return 0;
}


总之,虽然是裸的exgcd题,但是很容易被细节实现坑到,尤其是求最小非负整数解和处理负数的地方。

完结撒花~~~~

上一篇:A/B(扩展欧几里得)


下一篇:README.old