/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 450 点
問題文
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)
制約
- 2 \leq M \leq 1000
- 0 \leq A, B \leq M-1
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
M A B
出力
答えを 1 行に出力せよ。
入力例 1
4 1 2
出力例 1
7
問題文中の条件を満たす整数組は (x,y) = (1,1), (1,3), (2,1), (2,2), (2,3), (3,1), (3,3) の 7 通りです。
たとえば (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) となります。この数列の第 3 項は 8 であり、これは 4 の倍数です。よって、(x,y) = (3,2) は問題文中の条件を満たしません。
入力例 2
446 1 1
出力例 2
0
問題文中の条件を満たす整数組は存在しません。
入力例 3
1000 784 385
出力例 3
995373
Score : 450 points
Problem Statement
Among integer pairs (x, y) satisfying 0 \leq x,y \leq M-1, how many are there such that the infinite sequence (s_1, s_2, \dots) defined by the following recurrence relation contains no multiples of M?
- s_1 = x
- s_2 = y
- s_n = A s_{n-1} + B s_{n-2} (n \geq 3)
Constraints
- 2 \leq M \leq 1000
- 0 \leq A, B \leq M-1
- All input values are integers.
Input
The input is given from Standard Input in the following format:
M A B
Output
Output the answer on one line.
Sample Input 1
4 1 2
Sample Output 1
7
The integer pairs satisfying the condition in the problem statement are (x,y) = (1,1), (1,3), (2,1), (2,2), (2,3), (3,1), (3,3), for a total of seven pairs.
For example, when (x,y) = (2,1), the corresponding sequence is (2,1,5,7,17,31,65,127,\dots). This sequence contains no multiples of 4. Thus, (x,y) = (2,1) satisfies the condition in the problem statement.
On the other hand, when (x,y) = (3,2), the corresponding sequence is (3,2,8,12,28,52,108,212,\dots). The third term of this sequence is 8, which is a multiple of 4. Thus, (x,y) = (3,2) does not satisfy the condition in the problem statement.
Sample Input 2
446 1 1
Sample Output 2
0
No integer pairs satisfy the condition in the problem statement.
Sample Input 3
1000 784 385
Sample Output 3
995373