是校内模拟题。

已知两个数 $x, y$，求有多少个正整数不能被 $ax + by, a\ge0, b\ge0$ 表示。

$1\le x, y\le 10^8$

题解：

考虑到若 $(x,y)\neq 1$ 那么一定输出 $-1$,所以我们只需要考虑 $(x,y)=1$ 的情况.

我们知到,若 $a_i(1\le i\le n)$ 构成模 $n$ 的完系,$k.m\in Z$，$(m,n)=1$，则 $k+ma_i(1\le i\le n)$ 也构成模 $n$ 的完系.

我们可以考虑模 $b$ 为 $1$ 到 $b-1$ 的每个值最小什么时候出现,那么显然此时我们不选 $b$,然后又由于上述性质,我们可以直接求出余数为每个值的最小值.

由此可知,答案为

$$\sum_{i=1}^{y-1}\lfloor\frac{ix}{y}\rfloor$$

简单化简即可得到答案.

问学长：