C/C++买不到的数目题解（内含数论重要结论）

前言

唤我沈七就行嘿嘿。

大一软件工程在读。

菜鸡蒟蒻想在博客中记录一些算法学习的心得体会，会持续更新C/C++方面的题解，方便理清思路和日后复习。如果还能结识一起敲代码的小伙伴的话就更好啦嘿嘿，因为实在是太弱了，肯定免不了错误百出。

欢迎批评指正，期待共同成长！

题目链接

题目描述

题解部分

涉及算法：数论、模拟

初次看此题时我也是一头雾水，

直到我发现这个其实数论中的结论题

如果 a,b 均是正整数且互质，

那么由 ax+by,x≥0,y≥0 不能凑出的最大数是 a*b−a−b。

证明过程

具体怎么用呢？

接着往下看就知道啦。

思路

1 .通读一遍题目之后，将题目抽象成数学问题，题目可以理解为

已知 a 、b，存在两个数 x 、 y，使得 a * x + b * y ！= c,求出 c 的最大值。

2 .而抽象出来的数学问题正好对应着前面提到的数论当中的一个重要结论，

如果 a,b 均是正整数且互质，

那么由 ax+by,x≥0,y≥0 不能凑出的最大数是 a*b−a−b。

具体的证明由于过于复杂，我就不在这做过多讲解了。

如果有兴趣的同学可参考一下y总在别的题目的题解当中的有关此结论的部分过程。证明过程

我的建议是可以直接跳过证明部分，直接牢记结论，当然如果对这种数学问题非常痴迷那肯定是很厉害啦。

有了这个神奇结论题目做起来就容易多了，代码也相对容易，完整代码如下

完整代码

C语言版

#include<stdio.h>
int main()
{   
    int n,m;
    scanf("%d%d",&n,&m);
    printf("%d",n*m-m-n);
    return 0;
}

C++版

#include <iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    cout<<n*m-m-n;
    return 0;
}

完结散花

太感谢你能看到这儿啦。

这次的讲解虽然简单，但我的过题经历却异常艰难，初次看题目的时候一头雾水，直到发现了这个神奇结论才得以轻松解决。所以才急忙跑来分享。

参考文章

https://www.acwing.com/solution/acwing/content/3165/