← 返回题目列表

AtCoder · abc446_e

H. 多个自由序列

中文机器翻译题面 查看原题

分数: 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