AT_abc446_e [ABC446E] Multiple-Free Sequences

在所有满足 $0 \leq x, y \leq M-1$ 的整数对 $(x, y)$ 中，有多少对使得通过如下递推式定义的无限序列 $(s_1, s_2, \dots)$ 不包含 $M$ 的倍数？ - $s_1 = x$ - $s_2 = y$ - $s_n = A s_{n-1} + B s_{n-2}$（$n \geq 3$）

输入从标准输入读入，格式如下： > $M$ $A$ $B$

输出一行，表示满足条件的整数对数量。

### 样例解释 1 满足题中条件的整数对为 $(x,y) = (1,1), (1,3), (2,1), (2,2), (2,3), (3,1), (3,3)$，共计七对。 例如，当 $(x,y) = (2,1)$ 时，对应的序列为 $(2,1,5,7,17,31,65,127,\dots)$。该序列中不包含 $4$ 的倍数。因此，$(x,y) = (2,1)$ 满足题目条件。 另一方面，当 $(x,y) = (3,2)$ 时，对应的序列为 $(3,2,8,12,28,52,108,212,\dots)$。该序列的第三项是 $8$，是 $4$ 的倍数。因此，$(x,y) = (3,2)$ 不满足题目条件。 ### 样例解释 2 没有整数对满足题中条件。 ### 数据范围 - $2 \leq M \leq 1000$ - $0 \leq A, B \leq M-1$ - 输入均为整数。 由 ChatGPT 5 翻译