先来看看牛客网的入门题
题目描述
Chranos是个数学天才。
一天，有一个可爱的小女孩追求Chranos，他知道Chranos最喜欢当且仅当总质量为K克的时候的番茄炒蛋了。她希望通过美食俘获Chranos的胃，这样就一定可以和他在一起了吧！虽然小女孩有无限数量的食材，但是数学王国的番茄和蛋非常特殊，他们的质量分别为N克和M克。为了表现一颗完整的心、表达充足的爱意，所有的食材必须被用完。N和M都是正整数且互素，制作过程中既不会凭空增加质量，也不会凭空消失质量。
Chranos不希望小女孩打扰他学数学。他发现，并不是所有番茄炒蛋都是可以被制作出来的。他想找出最大的不可以被制作出的总质量K来拒绝小女孩，这样Chranos就可以永远和数学在一起了！
输入描述:
第一行为正整数N和M(2 \leq N, M \leq 50000)(2≤N,M≤50000)。
输出描述:
输出最大的不可以被制作出的总质量K。
示例
输入
2 3
输出
1
思路
可以通过找规律得到答案，但比较繁琐，所以还是选择找相关的数学知识来解决
这里应用到塞瓦维斯特定律，具体证明则需要用到裴蜀定律
塞瓦维斯特定律：已知a,b为大于1的正整数，gcd（a,b）=1，（a,b的最大公约数=1）则使不定方程ax+by=C不存在非负整数解的最大整数（C是最大的使不定方程 没有 非负整数解 的数。）C=a×b−a−b
（需要看证明的移步到最下方）
通过这个定律就可以很容易写出代码。不过需要注意数据范围，所以记得开long long
代码
#include<stdio.h>
#include<math.h>
int main(){
int n,m;
scanf("%d %d",&n,&m);
printf("%ld",n*m-n-m);
}
接下来我们再看一下NOIP原题
题目描述
小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小 凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在 小凯无法准确支付的商品。
输入格式
两个正整数 $a$ 和 $b$，它们之间用一个空格隔开，表示小凯中金币的面值。
输出格式
一个正整数 $N$，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。
样例 #1
样例输入 #1
3 7
样例输出 #1
11
提示
【输入输出样例 1 说明】
小凯手中有面值为 $3$ 和 $7$ 的金币无数个，在不找零的前提下无法准确支付价值为 $1,2,4,5,8,11$ 的物品，其中最贵的物品价值为 $11$，比 $11$ 贵的物品都能买到，比如：
$12 = 3 \times 4 + 7 \times 0$；
$13 = 3 \times 2 + 7 \times 1$；
$14 = 3 \times 0 + 7 \times 2$；
$15 = 3 \times 5 + 7 \times 0 $。
【数据范围与约定】
对于 $30\%$ 的数据： $1 \le a,b \le 50 $。
对于 $60\%$ 的数据： $1 \le a,b \le 10^4 $。
对于$ 100\%$ 的数据：$1 \le a,b \le 10^9 $。
思路
牵扯到数学定律应用的题目一般不会有太多新意，而更重在日常的积累。本题很明显也是直接用公式就行
代码
#include<stdio.h>
#include<math.h>
int main(){
int n,m;
scanf("%d %d",&n,&m);
printf("%ld",n*m-n-m);
}
定律证明
先证明a×b−a−b一定不能被取到。
利用反证法，我们假设存在x,y⩾0满足ax+by=ab−a−b。
移项得：a（x+1）+b（y+1）=ab①。
我们再将ab除到左边来，即a（x+1）/ab+b（y+1）/ab=1，在消一下即可得到（x+1）/b+（y+1）/a=1
那么a/（y+1）,b/（x+1）
简单证明一下上一句话：我们再返回①式，再将其一项，可以得到b（y+1）=a（b−x−1），
又∵gcd（a,b）=1，∴a/（y+1），b/（x+1）同理。
又∵a（x+1）+b（y+1）⩾a×b+b×a=2ab（∵b|（x+1） ∴b⩽x+1，对于a⩽y+1同理）。
这与我们假设中的a（x+1）+b（y+1）=ab,a⩾0,b⩾0矛盾。
∴假设不成立，即不存在x,y⩾0，满足ax+by=ab−a−b。
∴在原题中a×b−a−b一定不会被取到。
现在我们在来证明对于任意正整数C⩾ab−a−b+1一定能被取到。
移项得：C+a+b⩾ab+1。
不妨设k,m使其满足C+a+b=ka+m（k⩾b,1⩽m⩽a−1）。
又∵gcd（a,b）=1，可以由裴蜀定理
（在数论中，裴蜀定理是一个关于 最大公约数 （或最大公约式）的定理。. 裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何 整数 a、b和它们的最大公约数d，关于未知数x和y的线性 丢番图方程（称为裴蜀 等式 ）：. ax + by = m. 有解 当且仅当 m是d的倍数。. 裴蜀等式有解时必然有无穷多个整数解，每组解x、y都称为裴蜀数，可用 辗转相除法 求得。. 例如，12和42的最大 公因子是6，则方程12x + 42y = 6有解。. 事实上有（-3）×12 + 1×42 = 6及4×12 + （-1）×42 = 6。）
（若gcd（a,b）=1，则一定存在x,y∈Z，使得ax+by=1）得到如果x′,y′∈Z,−（b−1）⩽x′⩽−1，则一定存在整数y′使得ax′+by′=m。
简单证明一下上面这句话，∵在正整数x′的去之中一共有b−1个数，y′=（m−ax′）/b，一定可以找到x′使得b/（m−ax′）。
又∵ax′<0,m>0,b>0，∴y⩾1。
∴x=k+x′−1,y=y′−1。
又∵x,y⩾0。
∴ax+by=C
∴对于任意C⩾ab−a−b+1一定存在x,y⩾0满足ax+by=C