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 翻译