分数: 450 点
问题陈述
在整数对中 (x, y) 满意 0 \leq x,y \leq M-1,有多少个这样的无限序列 (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)
约束
- 2 \leq M \leq 1000
- 0 \leq A, B \leq M-1
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
M A B
输出
在一行上输出答案。
示例输入 1
4 1 2
示例输出 1
7
满足问题陈述中的条件的整数对是 (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
446 1 1
示例输出 2
0
没有整数对满足问题陈述中的条件。
示例输入 3
1000 784 385
示例输出 3
995373