AcWing_1205 买不到的数目(结论题)

AcWing

1205. 买不到的数目

引理：

给定$a$，$b$，若$d = gcd(a,b) > 1$，即$a$，$b$不是互质的，则一定不能凑出最大数。

结论：

如果$a$，$b$均是正整数且互质，那么由$ax + by, x \ge 0, y \ge 0$不能凑出的最大数是$(a - 1)(b - 1) - 1$

#include <bits/stdc++.h>
using namespace std;
int n, m;
int main(){
    cin >> n >> m;
    cout << (n - 1) * (m - 1) - 1;
    return 0;
}

补充：

裴蜀定理

对任何整数$a$、$b$和$m$，关于未知数$x$和$y$的线性丢番图方程（称为裴蜀等式）$ax+by=m$，有整数解时当且仅当$m$是$a$及$b$的最大公约数$d$的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解$x$、$y$都称为裴蜀数，可用扩展欧几里得算法求得。

例如，$12$和$42$的最大公约数是$6$，则方程$12x+42y=6$有解。事实上有$(-3) \times 12 + 1 \times 42 = 6$及$4 \times 12 + (-1) \times 42 = 6$.

特别来说，方程$ax+by=1$有整数解当且仅当整数$a$和$b$互素。