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

# 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=ax+by\ (x,y\in N)$ 我们再考虑$n-1$可以怎么表示。注意到$gcd(a,b)=1$，于是我们就可以把$n-1$中的$1$也用$a,b$的线性组合表示。 $n-1=ax+by-(ax_0+by_0)=a(x-x_0)+b(y-y_0)\quad$（这里$ax_0+by_0=1$） 由于$n-1$不能表示为$ax+by\ (x,y\in N)$的形式，所以$\forall (x_0,y_0),x-x_0<0$和$y-y_0<0$中至少有一个成立，即$x<x_0$和$y<y_0$中至少有一个成立。 首先，由$ax_0+by_0=1$，$x_0$和$y_0$必定不能同号。所以，当$x_0>0$时，$y_0\le0$，$y-y_0\ge y\ge0$，必须有$x-x_0<0$成立，即有$x<x'$（$x'$为最小的非负$x_0$），同理$y<y''$（$y''$为最小的非负$y_0$）。要注意的是，这里的$x',y''$并不是$ax_0+by_0=1$的一组解，而是相互独立的$x_0$最小的非负整数解和$y_0$最小的非负整数解。 因为我们要求的是$n$的最大值，$x,y$要尽量大，所以$x,y$均取最大值，即$x=x'-1,y=y''-1$ 再将$(x',y'')$代入，即可得到$n=a(x'-1)+b(y''-1)$，即$Ans=a(x'-1)+b(y''-1)-1$ 带一个$exgcd$先解出一组$(x_0,y_0)$，再算出$x',y''$，代入求解即可。 $Code:$ ```cpp #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\ $](https://www.luogu.org/space/show?uid=36998)神佬，他的这个思路真的是太妙了。 设$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$均非负，即为方程的一组非负整数解。 $Q.E.D.$