P3986 斐波那契數列

題目描述

定義一個數列：
$$f(0)=a,f(1)=b,f(n)=f(n?1)+f(n?2)$$

其中 a, b 均為正整數，n ≥ 2。

問有多少種 (a, b)，使得 k 出現在這個數列里，且不是前兩項。

由于答案可能很大，你只需要輸出答案模 10^9 + 7 的結果即可。

輸入格式

一行一個整數 k。

輸出格式

一行一個數，表示答案模 10^9 + 7的結果。

輸入輸出樣例 1

輸入 1

19260817

輸出 1

34166325

輸入輸出樣例 2

輸入 2

1000000000

輸出 2

773877569

說明/提示

1 ≤ k ≤ 10^9

EXP：

$$\begin{gathered} 針對于該函數數列中的數據分別為:a+b,a+2b,2a+3b,3a+5b即a,b的系數是斐波那契數列的數據。 \\ 1\le k\le 10^9,針對40項左右的斐波那契數就已經超過該范圍，并且a,b都是正整數。所以可以遍歷斐波那契數列判斷a. \\ k=af[x?1]+bf[x]=>bf[x]=k?af[x?1]=>b=(k?af[x?1])/f[x]因為a,b正整數的緣故。 \\ k?af[x?1]\equiv 0(modf[x])=>k\equiv af[x?1](modf[x]),因為gcd(f[x],f[x?1])=1 \\ a\equiv (k?f^{?1}[x?1](modf[x]))(modf[x])并且要保證b>0,即判斷a<k/f[x?1] \end{gathered}$$

# coding: utf-8
MOD = 10 ** 9 + 7def gcd_extended(a,b):"""擴展歐幾里得算法返回一個元組(d,x,y) 使得 d = gcd(a,b) = ax + by"""if a == 0:return (b,0,1)gcd , x1 , y1 = gcd_extended(b % a , a)x = y1 - (b // a) * x1y = x1return (gcd,x,y)def mod_inverse(a,m):"""求模逆元使用擴展歐幾里得算法返回a在m下的逆元如果沒有逆元返回None"""gcd, x, y = gcd_extended(a,m)if gcd != 1:return None # 如果a 和 m不互素else:return x % m # 返回逆元def matrix_mul(A, B):"""矩陣乘法"""return [[sum(a * b for a, b in zip(col, row)) for col in zip(*B)] for row in A]def matrix_pow(A, n):"""矩陣快速冪"""size_ = len(A)if n == 0:res = [[0 for _ in range(size_)] for _ in range(size_)]for i in range(size_):res[i][i] = 1elif n == 1:return Aelse:y = matrix_pow(A, n // 2)if n & 1:return matrix_mul(matrix_mul(y, y), A)return matrix_mul(y, y)K = int(input())
counter = 0
A = [[0, 1],[1, 1]
]
# 遍歷前面的斐波那契數列
for i in range(2,42):temp = matrix_mul([[0,1]],matrix_pow(A,i - 1))f_x = temp[0][1]f_x_1 = temp[0][0]# 計算范圍內最小的aa = (K * mod_inverse(f_x_1,f_x)) % f_x# 求取k / f[x-1]	由于向下取整，所以b > 0時要求是個足夠大的正整數target = K // f_x_1 - 1if a < target:# 如果a = 0則a本身不在計算if a == 0:counter -= 1# 根據a的大小，加上a + k_counter * f[x] 的所有acounter = (counter + 1 + (target - a) // f_x) % MOD
print(counter)