Loading... # 题目描述 浩介太懒惰了。他不会给你任何传说，只会给你任务： 斐波那契数字的定义如下： - $f(1)=f(2)=1$ . - $f(n)=f(n-1)+f(n-2)$ $(3\le n)$ 我们把 $G(n,k)$ 表示为可被 $k$ 整除的 $n$ 个斐波那契数的索引。对于给定的 $n$ 和 $k$ ，计算 $G(n,k)$ 。 由于这个数字可能太大，所以用 $10^9+7$ 的模来输出。 例如 $G(3,2)=9$ ，因为能被 $2$ 整除的 $3$ rd斐波那契数字是 $34$ 。 $[1,1,\textbf{2},3,5,\textbf{8},13,21,\textbf{34}]$ . # 输入 **输入** 输入数据的第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) - 测试用例数。 第一行也是唯一一行包含两个整数 $n$ 和 $k$ （ $1 \le n \le 10^{18}$ , $1 \le k \le 10^5$ ）。 保证所有测试用例中 $k$ 的总和不超过 $10^6$ 。 输入数据的第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ ）--测试用例数。第一行也是唯一一行包含两个整数 $n$ 和 $k$ （ $1 \le n \le 10^{18}$ , $1 \le k \le 10^5$ ）。保证所有测试用例中 $k$ 的总和不超过 $10^6$ 。 # 思路 ## 打表 由于要求的是可以被$k$整除的斐波那契数列，不妨先打表求一下斐波那契数列每一项模$k$的值的大小： ```bash # 当 k = 3 时有 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 1 ``` 可以看到0的出现是由顺序的， 每隔4个数字出现一个0 因此可以打表求出第一个可以被$k$整除的数字出现的位置，由于具有周期性，因此乘以$n$就是第$n$个可以被$k$整除的数字出现的位置 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #define endl '\n' using namespace std; const int N = 2e5 + 10; const int mod = 1e9 + 7; typedef long long LL; int t; LL n; int k; LL f1, f2, f3; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while(t --) { cin >> n >> k; if(k == 1) { cout << n % mod << endl; continue; } f1 = f2 = 1; for(int i = 3; ; i ++) { f3 = (f1 + f2) % k; f1 = f2; f2 = f3; if(f3 % k == 0) { cout << (n % mod * i % mod) % mod << endl; break; } } } return 0; } ``` ## 性质 这道题目涉及到了**斐波那契数列的模n特性--披萨诺周期** 即模$m$意义下斐波那契数列的最小正周期被称为**皮萨诺周期** 皮萨诺周期总是不超过$6m$，且只有在满足 $m=2\times 5^k$的形式时才取到等号 因此可以暴力枚举数列 最后修改：2025 年 01 月 11 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏