题目链接: https://vjudge.net/contest/540139#problem/E

题意

给出两个互素的正整数 x, y，求出一个最大的正整数 n，使得 ∀a,b∈N (ax+by != n)。

(也就是[n+1, +∞] ⊆ {ax+by(a,b∈N)})

0<x,y​≤1e9

思路

引理1

首先，对于互质的 x,y ，任何整数 k 都可以写成 k=cx+dy (c,d ∈ Z) 的形式。因为 ∃a,b (gcd(x,y)=ax+by)，而 gcd(x,y)=1，所以任意整数 n 可以写成 n(gcd(x,y)) 的形式。

证明

由 引理1 得，对于 k 所不能表达的数，必然有 (a<0 || b<0)。令 S = {k|k = ax+by (a<0||b<0, a,b ∈ Z)}，那么 S 为满足题意中不能被表达的数。

要求出 S 中所有元素 m = ax+by 的最大值，不妨先令 b=-1，再找找 a 的最大值。

显然，要满足 m ∈ S，在 b=-1 的情况下， a 的值可以取到[-∞, 0]。对于 a 正数的取值，我们一个一个考虑：

• m = x-y
• m = 2x-y
• m = 3x-y

...什么时候不满足 m ∈ S 呢？你可能想到了： a=y。此时有

• m = yx-y = (x-1)y

由题目条件， x>=1，可知 m 可以被表达为 ax+by (a,b ∈ N)，所以 m ∉ S。容易得到 max(a) = y-1。

所以 m 的最大值就是 (y-1)x - y = xy - x - y。

复杂度 O(1)。

代码

#include <iostream>

#define orep(i,l,r) for(auto i = (l); i < (r); ++i)
#define NL          std::cout << '\n';

int main() {
  std::ios::sync_with_stdio(0); std::cin.tie(0);

  int x, y; std::cin >> x >> y;
  std::cout << x*y-x-y;
  
  return 0;
}