题解 洛谷P1516 青蛙的约会

发布于 2019-06-09  107 次阅读


这是一道exgcd的板子题

前置知识:

1.裴蜀定理

裴蜀定理指出:关于整数𝑥,𝑦的不定方程 𝑎𝑥+𝑏𝑦=gcd⁡(𝑎,𝑏) 必定有解

那么我们怎么处理不定方程 𝑎𝑥+𝑏𝑦=c 方程的解呢?

  • 𝑐=gcd⁡(𝑎,𝑏) 此时据裴蜀定理有解。

  • 𝑐=𝑘∗gcd⁡(𝑎,𝑏) 我们先求出方程𝑎𝑥+𝑏𝑦=gcd⁡(𝑎,𝑏)的一组解,再将其乘上k

  • 𝑐⊥gcd⁡(𝑎,𝑏) 此时无解。 (⊥表示互质)

2.扩展欧几里德算法(exgcd)

由裴蜀定理我们已经知道了关于整数𝑥,𝑦的不定方程 𝑎𝑥+𝑏𝑦=gcd⁡(𝑎,𝑏) 必定有解,那么拓展欧几里得算法就能很好地帮助我们依靠代码实现求不定方程的一组解

一个小问题

如果我们知道了 𝑏𝑥+(𝑎%𝑏)𝑦=gcd⁡(𝑎,𝑏) 的解(𝑥,𝑦)

那么我们怎么推出 𝑎𝑥′+𝑏𝑦′=gcd⁡(𝑎,𝑏) 的解(𝑥′,𝑦′)?

avatar

这里只需要把a%b打开来变成a- \lfloor \frac{a}{b} \rfloor ,然后一一对应就好了

有了这两个前置知识,我们就可以非常快乐地切这道题了

首先我们可以发现,这道题的大致意思就是让我们求下面这个方程的解:

x+km≡y+kn(mod l)

根据模的性质,我们可以把这个式子给转换一下,变成x+km=y+kn-z*l(z是整数)

换一下位置,式子就变成了k*(m-n)+z*l=y-x

这样就变成了exgcd的模板啦~!

但是我们测来测去。。额。。只有80分

这里就涉及到了一个exgcd求最小解的问题

这是一个比较神奇的式子

我们将上面这个式子打开就变成了ax+by=c,这个式子可以使求出来的x,y为最小解

#include<iostream>
#include<cmath>
#define int long long
#define pr pair<int,int>
#define x tmp.first
#define y tmp.second
using namespace std;
pr exgcd(int a,int b)
{
    if (b==0) return pr(1,0);
    pr tmp=exgcd(b,a%b);
    return pr(y,x-a/b*y);
}
int gcd(int a,int b)
{
    if (b==0) return a;
    return (gcd(b,a%b));
}
signed main()
{
    int a,b,m,n,l;
    cin>>a>>b>>m>>n>>l;
    if (m<n) swap(m,n),swap(a,b);//防止出现负数的情况
    //k(m-n)+zl=b-a
    int c=gcd(m-n,l);
    if ((b-a)%c!=0) {cout<<"Impossible"<<endl; return 0;}//互质无解
    pr tmp=exgcd((m-n),l);//求方程的一组解
    int ans=l/gcd(m-n,l);//最后对ans取模得到解,ans可以缩小答案的范围
    cout<<((x*(b-a)/c)%ans+ans)%ans<<endl;//将答案乘上k以后再取模
    return 0;
}