Luogu P3951 小凯的疑惑(2017 TG Day1 T1)

jszjinshengzhi · 2018-10-18 18:12:20 · 题解

Luogu P3951 小凯的疑惑(2017 TG Day1T1)

题意：给定正整数a,b满足gcd(a,b)=1，求最大的不能表示为ax+by\ (x,y\in N)的形式的。

数据范围：1≤a,b≤10^9

分析：题目虽然要求的是最大的不能表示为ax+by的形式的数，但我们可以通过这个数+1来求，我们设这个数为n，则有：

我们再考虑n-1可以怎么表示。注意到gcd(a,b)=1，于是我们就可以把n-1中的1也用a,b的线性组合表示。

再将(x',y'')代入，即可得到n=a(x'-1)+b(y''-1)，即Ans=a(x'-1)+b(y''-1)-1

带一个exgcd先解出一组(x_0,y_0)，再算出x',y''，代入求解即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll t;
void exgcd(ll a,ll b,ll& x,ll& y){
    if(!b){
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    t=x;
    x=y;
    y=t-a/b*y;
}

ll a,b,x,y,xx,yy;
int main(){
    scanf("%lld%lld",&a,&b);
    exgcd(a,b,x,y);
    t=x/b;
    x-=t*b;
    y+=t*a;
    for(;x<0;)x+=b,y-=a;
    xx=x;
    for(;x>0;)x-=b,y+=a;
    yy=y;
    printf("%lld\n",a*(xx-1)+b*(yy-1)-1);
    return 0;
}

但是这并不是最优解，因为还有一个ab-a-b的神仙式子可以秒掉此题。其实我们可以将之前的式子Ans=a(x'-1)+b(y''-1)-1继续化简，把x'和y''给化掉。

因为(x',y')和(x'',y'')为不定方程ax_0+by_0=1的两组不同的解，所以我们就想办法把这两组解联系在一起。

注意到有x''=x'+tb,y''=y'-ta(t\in Z)

因为(x'',y'')为y_0最小且非负的解，易知x''最大且非正的x_0。而x'为最小且非负的x_0，那么这两组解就是连续的两组解了，也就是说t=-1，于是y''=y'+a

所以，Ans=ax'-a+by''-b-1=ax'+by'+ab-a-b-1=ab-a-b

其实这个结论可以通过与exgcd无关且简单的多的方法证明

如果你足够欧皇稍微试一下的话，很容易发现，方程ax+by=ab-a-b有两组解(b-1,-1),(-1,a-1)，通过其通解形式x=x_0+tb,y=y_0-ta（x_0,y_0是方程的任意一组解）不难发现这是连续的两组解（因为-1=(b-1)-b,a-1=-1+a）。当t递增时，x递增，y递减，如果方程有非负整数解，必然会夹在这两组解中间，但这是连续的两组解，所以方程ax+by=ab-a-b没有非负整数解。

现在我们只需证明\forall c>ab-a-b,ax+by=c有非负整数解即可。

根据方程的通解x=x_0+tb,y=y_0+ty，并注意到x=x_0+tb可以换一种形式写出来：x\equiv x_0\ (mod\ b)，于是就很明显有：必存在一组解满足0\le x\le b-1。换句话说，对于任意一个不在这个范围里的x，我们可以将x一直进行加上b或者减去b的操作使x满足条件。将这个东西带进去用不等式瞎搞一通，有ax\le ab-a,by=c-ax\ge c-ab+a>ab-a-b-ab+a=-b，所以b\cdot(y+1)>0，又因为b>0，所以y+1>0,y\ge0。这样我们就构造出了任意ax+by=c>ab-a-b的非负整数解。

就这么没了？

就这么没了。

这里再附加一个小结论：若(a,b)=1，则0\thicksim ab-a-b中恰有一半，即\frac{(a-1)\cdot(b-1)}2个数能表示为(ax+by),x,y\in N

证明：因为能表示的个数恰好为总数的一半，所以先猜个结论（大胆猜结论，不用验证）：n与ab-a-b-n中恰有一个能表示。

手动算两组，发现没毛病，那就开始证明。

证明很显然分为两部分：两个数不能都可以表示，两个数不能都不可以表示。

前者很显然，因为如果n与ab-a-b-n都能够表示，那么只用将它们加起来就能表示出ab-a-b，与前面的结论矛盾。

后者就很烦了。

首先\%\%\%\ ljc1301\ 神佬，他的这个思路真的是太妙了。

设ax+by=n无非负整数解，然后问题就转化为了构造ax+by=ab-a-b-n的非负整数解。

怎么去构造呢？还是套路，构造出ax+by=ab-a-b与ax+by=n的特解，并利用这两组解的不等关系来构造。

注意到ax+by=ab-a-b有一组特解x=b-1,y=-1，于是我们的目标就变成了在另一条方程里面寻找能与这组解构成不等关系的特解。

我们将ax+by=n的通解写出来：x=x_0+tb,y=y_0-ta，可知存在一组解满足0\le x\le b-1，再根据我们一开始的假设，方程ax+by=n无非负整数解，而x\ge0，所以y<0，即方程ax+by=n有解(x',y')满足0\le x'\le b-1,y'\le-1。

将上述两个方程的解带进去，有ab-a-b-n=a\cdot(b-1)-b-(ax'+by')=a\cdot(b-1-x')+b(-y'-1)，而根据上面的不等式，b-1-x'与-y'-1均非负，即为方程的一组非负整数解。