题解 P3951 【小凯的疑惑】

· · 题解

本篇题解upd于2018年8月25日。

本篇题解的原题解有很多争议，在这里稍微补充一下：

假设两种钱的面额为a和b，且\gcd(a,b)=1。

假设两种钱每种最少要拿一次(也就是不能不拿)，那么不能凑成的最大钱数k=a\times b(注意是最大钱数，我刚才打错了)，由于可以不拿，那么就把多拿的两张钱减去，也就是ans=k-a-b=a\times b-a-b，其实这里大家都应该比较透彻，但是这个为什么k=a\times b我在下面证明一下。

现在我们需要证明ax+by=k(x,y>0)无解。

我们利用反证法，设k=a\times b，假设ax+by=k(x,y>0)有解。

那么根据欧几里得算法，ax+by=s(s是任意整数)有解的条件是\gcd(a,b)|s。而这里\gcd(a,b)=1，满足条件。

我们假设找到了ax+by=1的一个解为(x_0,y_0)，那么就有ax_0+by_0=1。因为a,b\ge1，直觉告诉我们x_0\le0或者y_0\le0，这个不用我证明了吧。

等式两边同时乘以k，得到akx_0+bky_0=k，即k=ax+by的一个解为(kx_0,ky_0)，根据通解公式，通解为\begin{aligned}\left(kx_0+\frac {bt} {\gcd(a,b)},ky_0-\frac {at} {\gcd(a,b)}\right)\end{aligned}(t\in \rm Z)。因为gcd(a,b)=1，所以通解为(kx_0+bt,ky_0-at)。因为k=a\times b>0，而x_0\le 0或y_0\le0，所以x\le0或y\le0。当我们改变t的值时，把通解转化一下(b(ax_0+t),a(by_0-t))观察这个式子，我们会发现其中一定有一个会\le0的。我们继续转化，令X=ax_0+t，令Y=by_0-t，则X+Y=1。因为他们都是整数，所以X\le0或Y\le0的。而a,b>0,x=aX,y=bY，所以x\le0或y\le0，即ax+by=k(x,y>0)无解。

证毕。

为了严谨，我们还需要证明ax+by=k+r(x,y>0,r是正整数)有解。和上面思路差不多，为了严谨，我重新写一遍思路吧。

现在我们需要证明ax+by=k+r(x,y>0,r是正整数)有解。

那么根据欧几里得算法，ax+by=s(s是任意整数)有解的条件是\gcd(a,b)|s。而这里\gcd(a,b)=1，满足条件。

我们假设找到了ax+by=1的一个解为(x_0,y_0)，那么就有ax_0+by_0=1。因为a,b\ge1，直觉告诉我们x_0\le0或者y_0\le0，这个不用我证明了吧。

等式两边同时乘以k+r，得到a(k+r)x_0+b(k+r)y_0=k+r，即k+r=ax+by的一个解为(kx_0+rx_0,ky_0+ry_0)，根据通解公式，通解为\begin{aligned}\left(kx_0+rx_0+\frac {bt} {\gcd(a,b)},ky_0+ry_0-\frac {at} {\gcd(a,b)}\right)\end{aligned}(t\in \rm Z)。因为gcd(a,b)=1，所以通解为(kx_0+rx_0+bt,ky_0+ry_0-at)即(abx_0+rx_0+bt,aby_0+ry_0-at)。现在我们需要证明他们俩都大于0有解。

我们还是转化一下，通解转化为\begin{aligned}\left({b\left(ax_0+\frac{rx_0}b+t\right),a\left(by_0+\frac{ry_0}a-t\right)}\right)\end{aligned}，注意这里的除法是实数除法。那么现在需要证明\begin{aligned}ax_0+\frac{rx_0}b+t\end{aligned}和\begin{aligned}by_0+\frac{ry_0}a-t\end{aligned}都大于0。令X=\begin{aligned}ax_0+\frac{rx_0}b+t\end{aligned}，Y=\begin{aligned}by_0+\frac{ry_0}a-t\end{aligned}，则\begin{aligned}X+Y=ax_0+by_0+\frac{rx_0}b+\frac{ry_0}a=1+r\frac{ax_0+by_0}{ab}=1+\frac r {ab}>1\end{aligned}。注意到这个式子中X和Y一定可以构造出X和Y都大于0的解。

为什么呢？这个其实很好想，你可以把\begin{aligned}ax_0+\frac{rx_0}{b}\end{aligned}和\begin{aligned}by_0+\frac{ry_0}{a}\end{aligned}想象成任意两个和大于1的实数，你每次可以做的操作是把他们其中一个加1另一个-1，那么他们一定可以同时为正。如何证明？我们建立一个坐标系uOv(实在没字母可用了)，然后建立参数方程\begin{aligned}u=ax_0+\frac{rx_0}{b}+t\end{aligned}，\begin{aligned}v=by_0+\frac{ry_0}{a}-t\end{aligned}，其中t是参数，t\in\rm Z，我们先假设t\in\rm R，那么方程就是一条斜率为-1的直线，因为u+v>1，所以直线在第一象限的长度大于\sqrt2。因为t\in\rm Z，t\in\rm Z时候的图像就是在t\in\rm R情况上的一系列间距为\sqrt 2的点，而t\in\rm R时候的图像在第一象限内长度大于\sqrt2，所以t\in\rm Z时候的图像在第一象限内存在点。

所以x>0并且y>0的解一定存在。

证毕。

备注：

原本大概的思路是我这么yy出来的，是我在上课走神的时候想出来的，据我回忆，大概是这么想的：见下(我脑洞可能比较大)

嗯这个ans=a*b-a-b这个a和b不是很透彻，移项移走。

变成了ans+a+b=a*b，嗯，就是把答案两种面值钞票各加一个不得了

那么不就变成了两种钞票每一种最少取一个了吗

这个结论好像挺对，发个题解吧。

然后就过了，然后评论里就有不透彻的和说这个思路不对的，但是我觉得我一开始想的时候是从正确的结果想回推的所以结论一定是对的就是这个证明.....当时没想出来

然而这道题我考试时候写的45pts暴力，(然后与省一无缘了)

这个反证法思路证明结论成立是评论里大佬@zyzzyzzyzzyz提供的，在此表示感谢。

不过他的反证法我没看懂，自己yy了一个= =

代码还是放一个吧。注意开long long

#include <cstdio>
#include <iostream>

using namespace std;

long long int a, b;

int main()
{
    scanf("%lld%lld", &a, &b);
    printf("%lld\n", a * b - a - b);
    return 0;
}

%dalao

至今本题解安全+透彻+清真+人品了，有不透彻(自己不透彻或者觉得题解有问题)可以发讨论/私信@ghj1222。以下是当时上课走神灵机一动的题解。

2018-02-21版本题解：

对于这道题的答案a * b - a - b 我有一个比较易懂的解释：

假设两种钱每种最少要拿一次（也就是不能不拿），不能凑成的最小钱数为k，因为a和b互质，显然,k = a * b，(当k = a * b 时，由于ab互质，要么a拿b个，要么b拿a个)。

由于a和b可以一样都不拿，所以ans = k - a - b = a * b - a - b

于是代码略。。。