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

作者: wjyyy 分类: gcd/lcm,同余,数学,解题报告 发布时间: 2018-08-09 09:38

点击量:15

 

    不定方程求通解的一道题

 

题目描述

两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。

 

我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

 

输入输出格式

输入格式:

输入只包括一行5个整数x,y,m,n,L

 

其中0<x≠y < =2000000000,0 < m、n < =2000000000,0 < L < =2100000000。

 

输出格式:

输出碰面所需要的天数,如果永远不可能碰面则输出一行”Impossible”。

 

输入输出样例

输入样例#1:

1 2 3 4 5

输出样例#1:

4

题解:

    这个题目的条件很容易看出来,设两只青蛙的起点是\(s_1,s_2\),步长为\(x,y\)(题目的参数看着容易混淆)。那它们相遇的条件就是跳\(t\)步后\(s_1+tx\equiv s_2+ty(\mod L)\),求出\(t\)的最小值。

 

    可以把这个条件转化为另一个问题,因为这个式子是在\(\mod L\)的意义下进行的,把上面的式子移项得\(s_1-s_2+t(x-y)\equiv 0(\mod L)\),也就是\(s_1-s_2+t(x-y)= kL(k\in \mathbb{Z})\Rightarrow t(x-y)+kL=s_2-s_1\)。这样就是一个不定方程了,其中\((x-y),L,s_2-s_1\)都是常数。

 

    用扩展欧几里得解这个方程,可以得到\(t,k\)的一组特解,我们要求的是\(t\)的最小正整数解。我们回归到最基础的不定方程\(ax+by=d,d=\gcd (a,b)\),一个求通解的办法就是让\(x\)减去1,让\(y\)去平衡它,这样可以得到\(a(x-1)+b(y+\frac ab)=d\),要找出使得\(x-p\)为正整数且最小并满足\(y+p\times \frac ab\)为整数,那就要让\(a|p\)。因此\(p\in [0,x),a|p\),要让这个\(p\)在范围内尽可能大,我们就要找到一个最大的\(q\)使得\(aq<x\),这样最优解就是\(x-aq\)了。

 

    实际可以用gcd的思想来求解这个过程。因为不定方程有无数组解,我们抽出两个\(\left\{\begin{matrix}ax+by=d\\ ax’+by’=d \end{matrix}\right.\),上下相减得到\(a(x-x_0)=b(y_0-y)\),再让两边同除\(\gcd (a,b)\),得到\(\frac a{\gcd (a,b)}(x-x_0)=b\frac b{\gcd (a,b)}(y_0-y)\)。而\(\frac a{\gcd (a,b)} \bot \frac{b}{\gcd (a,b)}\),根据唯一分解定理可知\(\frac b{\gcd (a,b)}|(x-x_0)\),因此\(x_i=x_0+k\frac b{\gcd (a,b)}\)。所以\(k_0=k_i\mod \frac b{\gcd (a,b)}\)。

 

    最后注意如果\(d\)是\(\gcd(a,b)\)的倍数要乘上这个倍数。接着把原式中的”\(a,b\)”代作\((x-y),L\)即可。

 

Code:

#include<cstdio>
#include<cstring>
long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if(a==0)
    {
        x=1;
        y=0;
        return b;
    }
    long long d=exgcd(b%a,a,y,x);
    y-=b/a*x;
    return d;
}

int main()
{
    long long n,m,L,s1,s2;
    scanf("%lld%lld%lld%lld%lld",&s1,&s2,&n,&m,&L);
    if(n>m)//保证n<m,则系数>0
    {
        long long t=n;
        n=m;
        m=t;
        t=s1;
        s1=s2;
        s2=t;
    }
    long long a=m-n,b=L;
    long long x,y;
    long long t=exgcd(a,b,y,x);
    long long d=s1-s2;
    if(d%t!=0)
    {
        puts("Impossible");
        return 0;
    }
    d/=t;//最后答案要乘上的数
    L/=t;//求出最小解要mod上的数
    printf("%lld\n",((x*d)%L+L)%L);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */